Картинная галерея
В картинной галерее, имеющей форму N-угольника, расположено M люстр,
которые мы будем считать точечными источниками света. Точка стены галереи
называется освещенной, если из нее видна хотя бы одна из люстр.
Неосвещенным участком будем называть максимальное связное множество
точек стены галереи, ни одна из которых не освещена (участок может содержать
углы галереи). Напишите программу, определяющую все неосвещенные
участки.
Входные данные
Первая строка входного файла содержит два целых числа N и M (1 ≤
N, M ≤ 30). В каждой из следующих N строк записаны координаты очередного угла галереи.
Углы перечислены в порядке обхода стены по часовой стрелке. Далее идут M
строк, каждая из которых содержит координаты очередной из люстр. Все
координаты являются вещественными числами и разделяются пробелом.
Выходные данные
В единственную строку выходного файла выведите количество неосвещенных
участков.
Пример входного файла
5 1
0 0
0 5
4 5
2 3
5 0
3.0 1.0
Пример выходного файла
1
Решение
Рассмотрим решение задачи, если источник света один. Разобьем все стороны
N-угольника на отрезки так, чтобы каждый отрезок был либо целиком освещен,
либо целиком неосвещен. Для этого проведем из источника света лучи через те
вершины N-угольника, угол при которых больше 180o, и найдем ближайшие
точки пересечения этих лучей со сторонами N-угольника (касания не
рассматриваются). Эти точки и дадут нам требуемое разбиение. Теперь для
каждого отрезка надо проверить, освещен он или нет. Проведем луч из
источника света через середину проверяемого отрезка. Найдем точки
пересечения этого луча со сторонами N-угольника и среди них отыщем
наименее удаленную от источника света. Если это середина нашего отрезка, то
отрезок освещен, если нет, то та сторона, которой принадлежит эта точка,
закрывает проверяемый отрезок от источника света.
Проведем эту процедуру для остальных источников света, разбивая
имеющиеся неосвещенные отрезки на более мелкие (для освещенных отрезков
это бессмысленно). При подсчете соседние неосвещенные участки надо
объединить.