Олимпиадные задачи по программированию

Условие задачи

Плоское дно фонтана описывается замкнутой ломаной линией без самопересечений, причем никакие три вершины ломаной не лежат на одной прямой. Для организации подсветки фонтана между двумя заданными углами (вершинами) по дну проложен гибкий натянутый кабель.

Дно фонтана с протянутым кабелем подсветки

Требуется написать программу, вычисляющую минимальную длину этого кабеля.

Входные данные

Исходные данные записаны в файле INPUT.TXT в следующей последовательности:

• в 1-й строке - число вершин N (N≤100);
• в каждой из последующих N строк - пара чисел через пробел, являющихся координатами вершин x₁ y₁, x₂ y₂, ... x_N y_N в порядке обхода ломаной против часовой стрелки, где 1, 2, ... , N - номера вершин;
• в последней строке - номера соединяемых вершин k и l (1≤k

Координаты вершин являются вещественными числами.

Все входные данные корректны.

Выходные данные

Результат вывести в виде числа в файл OUTPUT.TXT. Результат проверяется с точностью до пяти значащих цифр. Результирующее число должно быть с фиксированной запятой.

7
2 0
5 0
6 3.5
5 6
4 2
3 7
0 5
3 7

7.5

Решение

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

Теперь, зная, что кабель может изменять направление только в углах фонтана, мы можем развивать идею решения дальше. Представим вершины ломаной вершинами графа, а те отрезки между вершинами, которые полностью лежат на дне фонтана, — его ребрами. При этом граф будет взвешенным и веса ребер будут равны расстояниям между вершинами. Далее, нам необходимо понять, существует ли такое ребро в графе вообще (т.е. проходит ли отрезок, соединяющий данные вершины, полностью по дну фонтана или в некоторый момент выходит за его пределы). Для этого нам надо научиться определять, пересекает ли данный отрезок ломаную: если он ее пересекает, то это автоматически означает, что он не проходит полностью по дну фонтана и соответствующего ребра в графе нет. Кроме того, отрезок может не пересекать границ фонтана, но полностью проходить вне него. Тогда он тоже непригоден, и нам надо научиться определять и этот случай. Несложно заметить, что если отрезок не пересекает ломаной, то достаточно проверить принадлежность многоугольнику лишь одной его точки, отличной от концов отрезка (например, его середину).

После того как построен граф, мы можем воспользоваться каким-либо алгоритмом поиска кратчайшего пути в графе — получившийся результат будет ответом на задачу.

Перейдем к техническим деталям реализации.

Будем перебирать все пары вершин и определять, принадлежит ли соединяющий их отрезок многоугольнику. Как написано выше, для этого нам надо узнать, пересекает ли отрезок ломаную и, в случае если пересечений нет, содержится ли его середина внутри ломаной.

Чтобы найти пересечения отрезка с ломаной, необходимо перебрать все ее звенья и для каждого проверить, пересекается ли оно с отрезком. То есть нам достаточно определить, пересекаются ли два отрезка, причем важен сам факт, а не координаты точки пересечения. Для этого достаточно такой проверки: если концы первого отрезка лежат по разные стороны прямой, содержащей второй отрезок, и, в свою очередь, концы второго отрезка лежат по разные стороны от прямой, содержащей первый, то эти отрезки пересекаются. Кроме того, чтобы корректно обрабатывать случай, когда отрезки лежат на одной прямой, введем дополнительное условие: должны пересекаться прямоугольники, охватывающие отрезки (т.е. отрезок является диагональю такого прямоугольника, а его стороны параллельны осям координат).

В вычислительной геометрии существует понятие ориентированной площади между векторами: по модулю она равна площади треугольника, образованного векторами, а ее знак совпадает со знаком ориентированного угла между векторами (т.е. зависит от порядка перечисления вершин). При этом ориентированная площадь треугольника будет равна S = (|a|•|b|•sin Ø) / 2, где a и b — векторы, совпадающие с двумя сторонами треугольника, а Ø — ориентированный угол между ними (т.е. угол от a до b). Несложно понять, что для того, чтобы точки C и D лежали по разные стороны от прямой AB, необходимо, чтобы площади треугольников ABC и ABD имели разные знаки (в силу свойств синуса, который имеет знак, совпадающий со знаком аргумента).

На плоскости удвоенная ориентированная площадь (или так называемое косое произведение) вычисляется как [a, b] = x₁•y₂ – x₂•y₁, где a = (x₁, y₁), b = (x₂, y₂). О выводе этого соотношения можно прочитать, например, в статье Е.В. Андреевой и Ю.Е. Егорова «Вычислительная геометрия на плоскости», которая доступна по адресу http://g6prog.narod.ru/cgeom.rar.

Таким образом, мы можем сформулировать условие пересечения двух отрезков:

[AB, AC]•[AB, AD] < 0 и [CD, CA]•[CD, CB] < 0 (косые произведения имеют разный знак, и их произведение отрицательно). Условие пересечения охватывающих многоугольников запишется следующим образом: X_max1 ≥ X_min2, X_max2 ≥ X_min1, Y_max1 ≥ Y_min2, Y_max2 ≥ Y_min1, где индексы max и min указывают на максимальное и минимальное значение соответственно, а цифры 1 и 2 означают принадлежность к первому или второму вектору.

Теперь перейдем к определению принадлежности точки многоугольнику. Для этого проведем луч из точки в произвольном направлении (например, налево) и посчитаем количество пересечений со сторонами многоугольника. Если оно окажется нечетным, то точка лежит внутри многоугольника, если четным — вне него. Действительно, уходящий в бесконечность конец луча обязательно лежит вне многоугольника, а при каждом пересечении состояние меняется (т.е. если идти слева снаружи многоугольника, то при пересечении его границы мы окажемся внутри него, после чего можем опять входить и выходить из него, изменяя состояние). Так как луч параллелен оси x, то определить, пересекается ли он со стороной многоугольника, гораздо проще, чем определять пересечение произвольного луча и отрезка. Пусть координаты точки, для которой мы ищем ее положение относительно многоугольника, (a, b). Тогда, чтобы луч, направленный из этой точки влево, пересекал отрезок, необходимо, чтобы нижняя точка отрезка лежала ниже луча, верхняя — выше и точка отрезка с y-координатой, равной b, — не правее a (т.е. a ≤ x). Условие «не правее» нам необходимо, чтобы корректно обрабатывать ситуации, когда отрезок совпадает со стороной многоугольника (кабель идет вдоль стены фонтана). При этом у нас могут возникнуть две исключительные ситуации: когда луч проходит через вершину многоугольника и когда сторона многоугольника полностью лежит на луче. В первом случае, если не рассматривать его отдельно, пересечение посчитается два раза. Избежать этого можно, если, например, не учитывать пересечение луча с нижней точкой отрезка (для одной из сторон многоугольника это будет верхняя точка, а для другой — нижняя, и в итоге она посчитается только один раз). А отрезки, принадлежащие лучу, можно смело игнорировать: вместе с первым условием это никак не изменит четности.

Итак, если отрезок не пересекает границ многоугольника и лежит внутри него, то мы можем создать ребро в графе, соединяющее соответствующие вершины, при этом вес ребра равен длине отрезка, которую легко можно посчитать, пользуясь теоремой Пифагора. Хранить граф будем в матрице смежности размером n•n, т.е. в случае наличия ребра между вершинами с номерами i, j в элементе матрицы dist[i][j] будет храниться его вес, а отсутствие ребра будем помечать особым образом, например –1. В данном случае все расстояния неотрицательные, так что –1 вполне подходит для признака отсутствия ребра.

Построив граф, мы должны вычислить длину кратчайшего пути от начальной вершины до конечной. Обычно для решения этой задачи используется алгоритм Дейкстры (сложность алгоритма O(N²)), однако в данном случае благодаря малой размерности задачи мы можем сэкономить свои силы и время и воспользоваться более простым в написании алгоритмом Флойда (который ищет кратчайший путь от каждой вершины до каждой и имеет сложность O(n³)).

Суть алгоритма Флойда заключается в следующем: если путь из вершины i в вершину j длиннее (или вовсе не существует), чем «кружной» путь через промежуточную вершину k, т.е. dist[i][j] > dist[i][k] + dist[k][j], то мы заменяем содержимое ячейки dist[i][j] на более короткий путь (dist[i][j] = dist[i][k] + dist[j][k]). Перебирая все возможные пары вершин и все промежуточные вершины и при необходимости заменяя пути (не забываем о «несуществующих» ребрах, помеченных –1!), мы получим полную таблицу кратчайших путей. При этом важен порядок следования циклов: промежуточная вершина (k) должна перебираться в самом внешнем цикле. Более подробно об алгоритме Флойда и графах в целом можно прочитать в курсе лекций Е.В. Андреевой, доступных по адресу: http://g6prog.narod.ru/aesclect.ru.

После этого нам достаточно просто вывести содержимое элемента dist[k][l] в требуемом формате и наслаждаться результатом проделанной работы.

От редакции

Уважаемые читатели! По досадной случайности решения задачи о чайнворде из прошлого номера не были выложены на диск. Мы постарались исправить недоразумение и опубликовали решения на диске, прилагаемом к этому номеру.