Задача 102934

Тема:    [ Прямая и отрезок ]

Сложность: 3 Классы: Название задачи: Картинная галерея .

Условие

В картинной галерее, имеющей форму N-угольника, расположено M люстр, которые мы будем считать точечными источниками света. Точка стены галереи называется освещенной, если из нее видна хотя бы одна из люстр. Неосвещенным участком будем называть максимальное связное множество точек стены галереи, ни одна из которых не освещена (участок может содержать углы галереи). Напишите программу, определяющую все неосвещенные участки.

Входные данные
Первая строка входного файла содержит два целых числа N и M (1 ≤ N, M ≤ 30). В каждой из следующих N строк записаны координаты очередного угла галереи. Углы перечислены в порядке обхода стены по часовой стрелке. Далее идут M строк, каждая из которых содержит координаты очередной из люстр. Все координаты являются вещественными числами и разделяются пробелом.

Выходные данные
В первую строку выходного файла выведите количество неосвещенных участков S. Каждая из следующих S строк должна содержать описание очередного из участков в виде тройки чисел, разделенных пробелом. Первые два числа определяют координаты начальной точки участка, третье – его длину. (Участок должен продолжаться на указанную длину в направлении обхода стены по часовой стрелке. Никакие два участка не должны иметь общих точек.) Числа, определяющие участок, должны быть выведены не менее чем с 3 верными значащими цифрами.

Пример входного файла
5 1
0 0
0 5
4 5
2 3
5 0
3.0 1.0

Пример выходного файла
1
1 5 5.82843

Решение

Скачать архив тестов и решений

Рассмотрим решение задачи, если источник света один. Разобьем все стороны N-угольника на отрезки так, чтобы каждый отрезок был либо целиком освещен, либо целиком неосвещен. Для этого проведем из источника света лучи через те вершины N-угольника, угол при которых больше 180^o, и найдем ближайшие точки пересечения этих лучей со сторонами N-угольника (касания не рассматриваются). Эти точки и дадут нам требуемое разбиение. Теперь для каждого отрезка надо проверить, освещен он или нет. Проведем луч из источника света через середину проверяемого отрезка. Найдем точки пересечения этого луча со сторонами N-угольника и среди них отыщем наименее удаленную от источника света. Если это середина нашего отрезка, то отрезок освещен, если нет, то та сторона, которой принадлежит эта точка, закрывает проверяемый отрезок от источника света.

Проведем эту процедуру для остальных источников света, разбивая имеющиеся неосвещенные отрезки на более мелкие (для освещенных отрезков это бессмысленно). При выводе соседние неосвещенные участки надо объединить.

Источники и прецеденты использования

книга
предмет	информатика
Автор	Беров В., Лапунов А., Матюхин В., Пономарев А.
Название	Особенности национальных задач по информатике
Издательство	Триада-С
Год издания	2000
глава
Номер	4
Название	Вычислительная геометрия
Задача
Номер	4