0 5

3 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.