2299. Теодор Рузвельт

“Теодор Рузвельт” – флагманский корабль флота Кукуляндии. Заклятые враги Кукуляндии, Плоскоземельцы, решили его уничтожить. Им стало известно, что “Теодор Рузвельт” задаётся выпуклым многоугольником с  вершинами, причём координаты всех его вершин им известны. Затем они выпустили  баллистических ракет и зафиксировали координаты точек их взрывов. По расчётам штаба Плоскоземельцев, “Теодор Рузвельт” будет уничтожен, если в него попадёт не менее k ракет. Определите, удалось ли Плоскоземельцам уничтожить корабль.

Вход. В первой строке заданы целые числа n, m и k (3 ≤ n ≤ 10⁵, 0 ≤ k ≤ m ≤ 10⁵). В следующих n строках указаны координаты вершин многоугольника в порядке против часовой стрелки. В следующих m строках заданы координаты точек взрывов. Все координаты – целые числа, не превосходящие по модулю 10⁹.

Выход. Выведите “YES”, если не менее k точек лежат внутри многоугольника, и “NO” в противном случае.

Пример входа	Пример выхода
5 4 2 1 -1 1 2 0 4 -1 2 -1 -1 -2 -1 1 -1 0 1 2 3	YES

РЕШЕНИЕ

геометрия + бинарный поиск

Анализ алгоритма

Рассмотрим задачу определения принадлежности точки выпуклому многоугольнику.

Пусть координаты вершин многоугольника заданы в порядке обхода против часовой стрелки: p₁, p₂, …, p_n. Зафиксируем вершину p₁. Тогда все остальные вершины упорядочены относительно неё по полярному углу.

Проведём из точки p₁ лучи, проходящие через остальные вершины (то есть диагонали многоугольника). Теперь можно применить бинарный поиск, чтобы найти такое ребро p_ip_i+1, для которого ориентации троек точек p₁p_iq и p₁p_i+1q различны.

Таким образом, мы определим сектор (треугольник), в котором может находиться точка q.

После того как найден угол p_ip₁p_i+1, в котором находится точка q, можно за константное время проверить, лежат ли точки p₁ и q по одну сторону от прямой p_ip_i+1. Для этого необходимо, чтобы ориентация тройки точек p_ip_i+1q была левой (поскольку ориентация p_ip_i+1p₁ является левой – вершины многоугольника заданы в порядке против часовой стрелки).

В начале алгоритма следует также проверить граничные случаи: если ориентация тройки p₁p_nq левая или ориентация тройки p₁p₂q правая, то точка q лежит вне многоугольника.

Направление поворота. Рассмотрим движение из точки А в точку В, а затем из точки В в точку С. Поворот считается левым (движение происходит против часовой стрелки), если векторное (псевдоскалярное) произведение AB ´ BC > 0, и правым – если AB ´ BC < 0.

Реализация алгоритма

Объявим структуру точка и массив точек.

#define MAX 100001

struct Point

{

long long x, y;

Point(long long x = 0, long long y = 0) : x(x), y(y) {}

};

Point p[MAX];

Функция angle определяет, является ли поворот при переходе через точки А, B, С левым или правым. Для этого вычислим соответствующие векторы:

AB = (b.x – a.x, b.y – a.y)

BC = (c.x – b.x, c.y – b.y)

Псевдоскалярное произведение AB ´ BC равно

= (b.x – a.x) * (c.y – b.y) – (b.y – a.y) * (c.x – b.x)

Знак этого выражения определяет направление поворота:

· положительное значение – левый поворот;

· отрицательное значение – правый поворот;

int angle(Point a, Point b, Point c)

{

long long q = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);

return (q > 0) - (q < 0); // sgn(q)

}

Функция inside возвращает true, если точка q лежит внутри многоугольника.

bool inside(Point q)

{

В качестве базовой выберем первую вершину многоугольника.

Point a = p[1];

Если ориентация тройки точек p₁p_nq является левой или ориентация тройки p₁p₂q является правой, то точка q лежит вне угла p_np₁p₂, а значит, и вне многоугольника.

if (angle(a, p[2], q) < 0 || angle(a, p[n], q) > 0) return false;

Запустим бинарный поиск на отрезке [l; r] = [2; n]. Ищем такие точки p_l и p_r (r = l + 1), что точка q лежит внутри угла p_lp₁p_r.

int l = 2, r = n, m;

while (l + 1 < r)

{

m = (l + r) / 2;

if (angle(a, p[m], q) < 0)

r = m;

else

l = m;

}

return angle(p[l], p[r], q) >= 0;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d %d", &n, &m, &k);

for (int i = 1; i <= n; i++)

{

scanf("%lld %lld", &x, &y);

p[i] = Point(x, y);

}

Вычисляем количество точек, лежащих внутри многоугольника.

res = 0;

for (int i = 1; i <= m; ++i)

{

scanf("%lld %lld", &x, &y);

if (inside(Point(x, y))) res++;

}

Выводим ответ.

if (res < k) puts("NO"); else puts("YES");