Условие: Номер 28

Задача 28. На плоскости задано N точек своими координатами и матрица C(N*N); C(i,j)=C(j,i)=1 в случае, если вершины i и j соединены отрезком и 0 иначе. Известно, что любая вершина соединена по крайней мере с двумя другими, и что отрезки пересекаются только в концевых точках. Таким образом, вся плоскость разбивается на множество многоугольников. Задана точка Z(x,y). Найти минимальный по площади многоугольник, содержащий Z, или выдать сообщение, что такого не существует. Если Z принадлежит какому-то отрезку, то выдать его концевые точки, если Z лежит в многоугольнике, то выдать его вершины в порядке обхода по контуру.

  Решение задачи: Номер 28

Решение задачи 28. Проверяем, лежит ли точка z на каком-либо отрезке. Если нет, то проводим отрезок, концевые точки которого z и, например, вершина 1. Находим ближайшую к z точку пересечения этого отрезка и сторон многоугольников, на которые разбивается плоскость. Пусть эта точка принадлежит стороне ab. Для этой стороны сначала определяем направление обхода (см. задачу 3); затем ищем следующую, смежную с текущей, сторону bc контура, которая образует минимальный по величине угол с отрезком ba (угол отсчитывается от отрезка ab по часовой или против часовой стрелки в зависимости от того, по или против часовой стрелки обход, сравнение углов - см. задачу 1). Находим замкнутый контур и определяем, находится ли точка z внутри него или снаружи. Если снаружи, то удаляем из фигуры все ребра этого контура и повторяем процесс. Пример:

Назад