Геометрические задачи на олимпиадах по информатике (стр. 3 из 3)
Домики Винни-Пуха и Кролика не могут находиться внутри ловушки, но могут находиться на ее границе.
Выведите в выходной файл одно число — длину самого короткого безопасного пути от домика Винни-Пуха до домика Кролика с тремя знаками после точки.
| Примеры входного файла | Примеры выходного файла |
| 0 0 0 1 10 10 1 | 1.000 |
| 5 0 0 5 0 0 5 | 7.854 |
| -5 0 5 0 0 0 3 | 11.861 |
Решение. Для решения этой задачи необходимо определять взаимное расположение окружности и отрезка (а не прямой!!!) и правильно вычислять длину дуги окружности, ограниченной двумя заданными точками.
Задача 6. Подсветка фонтана. (IX Всероссийская олимпиада по информатике)
Плоское дно фонтана описывается замкнутой ломаной линией без самопересечений, причем никакие три вершины ломаной не лежат на одной прямой. Для организации подсветки фонтана между двумя заданными углами (вершинами) по дну проложен гибкий натянутый кабель (см. рис.). Требуется написать программу, вычисляющую длину этого кабеля.
Исходные данные записаны в файле в следующей последовательности:
· в 1-ой строке — число вершин N(N£ 100);
· в каждой из последующих N строк — пара чисел через пробел, являющихся координатами вершин x1y1x2y2¼xN yNв порядке обхода ломаной против часовой стрелки, где 1, 2,..., N - номера вершин;
· в последней строке —номера соединяемых вершин kиl (1 £k<l£N).
Координаты вершин являются вещественными числами.
Результат вывести в виде числа. Результат проверяется с точностью до шести значащих цифр. Результирующее число может быть как с фиксированной точкой, так и в нормализованном виде.
| Пример входного файла | Пример выходного файла | |
| 72 05 06 3.55 64 23 70 53 7 | 7.5 | |
Решение. Возможно несколько различных подходов к решению данной задачи. Один из них — поиск кратчайшего пути в графе (см. лекцию 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.