Задача 36.
На местности, представляющей собой идеально ровную поверхность, стоит высокий забор. План забора представляет собой замкнутую ломаную без самопересечений. Эта ломаная задается N парами координат своих вершин в порядке обхода ограничиваемой забором области против часовой стрелки. Вершины пронумерованы от 1 до N, N<100.
В точке (x,y) стоит человек ((x,y) не может лежать на ломаной). Считая, что каждому звену ломаной становится в соответствие пара номеров концевых вершин, указать, какие звенья человек увидит полностью или частично в качестве невырожденного отрезка, а какие - вообще нет. Если при взгляде звено видно как точка или как пара, точек, то полагаем, что оно не видно.
|
Решение задачи 36.
Пусть точка z - центр координат (если это не так, сделаем параллельный перенос). Для того, чтобы звено забора было полностью видно, необходимо и достаточно, чтобы из точки z, где стоит человек, были видны обе вершины этого звена, и еще какая-нибудь его внутренняя точка. Будем считать, что вершина l звена видна, если интервал (z,l) не пересекает никаких звеньев забора, или же если обе концевые вершины пересекаемого звена k лежат на [z,l], т.е. человек смотрит вдоль звена k.
Отсортируем по неубыванию углы, образуемые с осью OX отрезками, одна концевая точка которых z, а вторая пробегает все вершины звеньев (углы отсчитываются от точки z в положительном направлении, т.е. против часовой стрелки). Получаем последовательность углов a1,a2, ,,, ,an. Добавляем в эту последовательность угол an+1=a1. Из точки z в направлении между прямыми, идущими под углами Li и Li+1 может быть виден кусок только одного единственного звена.
Из точки z под углами (ai+ai+1)/2, i=1, ... ,n, проводим лучи и для каждого луча смотрим, какое звено k этот луч пересекает первым (если первое пересечение происходит по вершине, то оно не рассматривается). В том случае, если у звена k видны обе вершины, то звено видно полностью, если хотя бы одна вершина не видна, то k видно частично.
После анализа точек пересечения всех n лучей те звенья, которые не видны ни полностью, ни частично, получают пометку невидимых.
|
