Касательные к многоугольнику
Поиск касательных к выпуклому многоугольнику, параллельных данной прямой
Пусть у нас есть выпуклый многоугольник $A_1 A_2 \ldots A_n$ (пусть обход многоугольника против часовой стрелки) и некоторая прямая. Мы хотим найти $2$ прямые, которые касаются многоугольника и при этом параллельны данной прямой. Найдем точки, в которых эти прямые будут касаться многоугольника. Рассмотрим вектор $v$ --- направляющий вектор данной прямой. Рассмотрим вектора $\overrightarrow{A_1 A_2}, \overrightarrow{A_2 A_3}, \ldots, \overrightarrow{A_n A_1}$ именно в таком порядке. Заметим, что они идут в порядке против часовой стрелки. Тогда если рассмотреть между какими соседними позициями в этом порядке находятся $v$ и $-v$, то эти позиции соответсвуют тем вершинам, в которых касательные касаются многоугольника. Для того, чтобы найти эти позиции надо сделать обычный $lower\_bound$.
Поиск касательных из точки к выпуклому многоугольнику за $O(\log n)$ на запрос
Пусть у нас есть выпуклый многоугольник $A_1 A_2 \ldots A_n$ (пусть обход многоугольника против часовой стрелки) и некоторая точка $P$. Мы хотим найти $2$ точки $A_i$ и $A_j$, такие что прямые $P A_i$ и $P A_j$ это касательные к многоугольнику или сказать, что точка $P$ лежит внутри многоугольника. Для проверки того, что точка лежит внутри многоугольника, будем использовать проверку за логарифм.
Пусть мы поняли, что точка лежит снаружи. Назовем сторону $A_i A_{i+1}$ левой, если $\angle(\overrightarrow{P A_i}, \overrightarrow{P A_{i+1}}) > 0$ или $\angle(\overrightarrow{P A_i}, \overrightarrow{P A_{i+1}}) = 0$ и $P A_i < P A_{i+1}$ и правой, иначе. Заметим, что если пойдем вдоль границы многоугольника, то на нем будут подряд идущие левые стороны и подряд идущие правые стороны, при этом те вершины, в которых тип поменяется, будут подходить как ответ. Как найти границы, в которых тип меняется?
Рассмотрим луч $P A_1$. Найдем его вторую сторону которая пересекается с этим лучом. Для этого заметим, что точки $A_2, A_3, \ldots, A_i$ лежат с одной стороны от этого луча, а $A_{i+1}, \ldots, A_n$ с другой. Поэтому этот момент можно найти простым бинпоиском. Теперь посмотрим типы сторон начиная от $A_1 A_2$ до $A_i A_{i+1}$ и на типы строк от $A_i A_{i+1}$ до $A_n A_1$. Заметим что на каждой из этой дуг теперь типы сначала одни, потом в точке касания меняются на другие и так до конца дуги. Поэтому на каждой из дуг можно сделать бинпоиск и найти точку касания.
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s