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