Численное решение геометрических задач

В ряде случаев при решении геометрических задач формулы из вычислительной геометрии могут оказаться слишком громоздкими и приводят к решению нелинейных уравнений. Тогда на помощь могут прийти численные (приближенные) методы, позволяющие решить задачу за требуемое время и с нужной точностью. Такой подход был продемонстрирован в [6] при рассмотрении задачи “Фонтан” (ее не следует путать с задачей 6, приведенной ниже).

Из численных методов наиболее часто употребимым является метод дихотомии (деления пополам). Рассмотрим его на примере задачи XII Всероссийской олимпиады по информатике.

Задача 3. Раздел царства.

Царство царя Гороха представляет собой выпуклый N -угольник, внутри которого расположены K селений. Царь решил завещать двум своим сыновьям по полцарства, одинаковые по площади и с равным количеством селений. Для этого он требует разделить царство одной прямолинейной границей.

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

Первая строка входного файла содержит количество вершин многоугольника N (3  N 5). В следующих N строках заданы координаты вершин многоугольника, перечисленные в порядке обхода контура по часовой стрелке. В (N +2)-ой строке указано количество селений K (0  K  1), а в последующих K строках заданы координаты селений. Все координаты — целые числа, не превосходящие по модулю 10⁶. Размерами селений следует пренебречь.

В выходной файл нужно вывести координаты любых двух различных точек, через которые следует провести границу. Координаты должны быть выведены с 6 знаками после десятичной точки.

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

Задача 4. Рандеву. (VII Всероссийская олимпиада по информатике.)

Локаторы дальней космической связи замечают летящий в плоскости орбиты земли неизвестный астероид с координатами (x, y). Астероид летит с постоянной скоростью, векторное значение которой равно (V_x, V_y). С земли из точки с координатами (0, 0) немедленно стартует ракета с радиусом действия R (R > 0). Ракета летит по прямой с постоянной скоростью в пределах от 0 до W.

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

Результат решения задачи должен быть вычислен с погрешностью не более 0.01. Влиянием земли и всех космических объектов пренебречь. Ракета и астероид двигаются в одной плоскости.

В начале входного файла содержится число N — количество наборов исходных данных (тестов). Далее расположены N наборов исходных данных; каждый набор — шесть вещественных чисел: X, Y, V_x, V_y, W, R. Все числа в исходном файле разделяются пробелами и (или) символами перевода строки.

Для каждого набора исходных данных вывести с новой строки вектор скорости (U_x, U_y) и минимальное время до встречи, либо сообщение “Встреча невозможна”.

Решение. Для решения этой задачи прежде всего необходимо уметь определять взаимное расположение прямой, вдоль которой движется астероид, и окружности с центром на Земле и радиусом R. Если они не пересекаются, то встреча невозможна, в противном случае требуется отыскать точки их пересечения. Затем для поиска точки встречи с минимальным временем можно опять же применить дихотомию.

Различные задачи

Задача 5. “Куда идем мы с Пятачком?” (Кировское открытое командное первенство по программированию, 2001 г.)

Пятачок и Винни-Пух каждое утро ходят пить чай в гости к Кролику. Естественно, самым коротким путем. К сожалению, однажды Винни-Пуху пришла в голову идея вырыть ловушку для Слонопотама. Самое обидное, что они с Пятачком ее даже вырыли. Поэтому теперь каждое утро, идя в гости к Кролику, они боятся в нее провалиться.

Напишите программу, которая посчитает длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика.

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

Во входном файле записаны сначала координаты домика Винни-Пуха X_В Y_В, затем — координаты домика Кролика X_К Y_К, а затем — координаты центра и радиус ловушки X_Л Y_Л R_Л. Все координаты — целые числа из диапазона от –32000 до 32000. Радиус ловушки — натуральное число, не превышающее 32000.

Домики Винни-Пуха и Кролика не могут находиться внутри ловушки, но могут находиться на ее границе.

Выведите в выходной файл одно число — длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика с тремя знаками после точки.

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

Задача 6. Подсветка фонтана. (IX Всероссийская олимпиада по информатике)

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

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

· в 1-ой строке — число вершин N (N £ 100);

· в каждой из последующих N строк — пара чисел через пробел, являющихся координатами вершин x ₁ y ₁ x ₂ y _{2 ¼} x_N y _N в порядке обхода ломаной против часовой стрелки, где 1, 2,..., N - номера вершин;

· в последней строке —номера соединяемых вершин k и l (1 £ k < l £ N).

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

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

Решение. Возможно несколько различных подходов к решению данной задачи. Один из них — поиск кратчайшего пути в графе (см. лекцию 8), в матрице смежности которого записаны расстояния между вершинами границы фонтана, если их можно напрямую соединить шлангом и ¥, если этого сделать нельзя. Для построения такой матрицы необходимо уметь проверять наличие пересечения двух отрезков и в случае отсутствия пересечений — местоположение отрезка относительно границы фонтана (внутри или снаружи он находится). В последней подзадаче достаточно определить местонахождение одной из внутренних точек этого отрезка.

Знание различных геометрических формул было необходимо и при решении задачи XIII Всероссийской олимпиады по информатике “Пожар” (см. [7]).

Заключение

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

Литература

1. Препарата Ф., Шеймос М. Вычислительная геометрия: введение. — М.: Мир, 1989.

2. Окулов С.М. Геометрические алгоритмы. “Информатика”, №15, 16, 17, 2000.

3. Окулов С.М. 100 задач по информатике. Киров: изд-во ВГПУ, 2000.

4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.

5. Андреева Е., Фалина И. Турбо-Паскаль в школе. М.: Изд-во Бочкаревой Н.Ф., 1998.

6. Станкевич А. С. Решение задач I Всероссийской командной олимпиады по программированию. “Информатика”, №12, 2001.

7. Андреева Е.В. Решение задач XIII Всероссийской олимпиады по информатике. “Информатика”, №19, 2001.