Решение задачи 6.
Простейшим решением случая а) является просмотр координат вершин N-угольника и определение, совпадают ли координаты одной из них с координатами точки (X,Y). Очевидно, что в этом случае необходим просмотр всех элементов массива.
Однако возможно существенно сократить количество операций, используя метод дихотомии.
Сравним вначале координату первой вершины в обходе с координатами точки (X,Y). Если они совпадают, то задача решена. Иначе определим индексы начальной и конечной точек интересующего нас обхода. Очевидно, что вначале они равны 2 и N соответственно. Пусть на некотором шаге индексы начальной и конечной точек интересующего нас обхода равны f и l соответственно. Определим индекс средней точки обхода m=(f+l) div 2.
Определяем теперь положение точки (X,Y) и точки с индексом f относительно прямой, проходящей через точки с индексами 1 и m. Возможны следующие ситуации:
1. Точки лежат по одну сторону от прямой.
В этом случае нас не интересует часть обхода от точки с индексом m до точки с индексом l. Поэтому последней интересующей нас точкой в обходе можно считать точку с индексом m-1. Поэтому пола гаем l:=m-1.
2. Точки лежат по разные стороны от прямой.
В этом случае нас не интересует часть обхода от точки с индексом f до точки с индексом m-1. Поэтому первой интересующей нас точкой в обходе можно считать точку с индексом m. Поэтому полагаем f:=m.
Процесс оканчивается, когда в интересующем нас обходе оста лось только две точки, т.е. l-f=1. Осталось проверить только их координаты на требуемое свойство.
|
