ння фонтану. ( IX Всеросійська олімпіада з інформатики )
В
Плоске дно фонтану описується замкнутою ламаною лінією без самоперетинів, причому ніякі три вершини ламаної чи не лежать на одній прямій. Для організації підсвічування фонтану між двома заданими кутами (вершинами) по дну прокладений гнучкий натягнутий кабель (див. рис.). Потрібно написати програму, яка обчислює довжину цього кабелю. p> Вихідні дані записані у файлі в наступній послідовності:
В· в 1-ої рядку - число вершин N ( N ВЈ 100);
В· в кожному з наступних N рядків - пара чисел через пропуск, які є координатами вершин x 1 y 1 x 2 y 2 Вј x N y N в порядку обходу ламаної проти годинникової стрілки, де 1, 2, ..., N - номери вершин;
В· в останньому рядку - номери з'єднуються вершин k і l (1 ВЈ k < l ВЈ N ).
Координати вершин є речовими числами.
Результат вивести у вигляді числа. Результат перевіряється з точністю до шести значущих цифр. Результуюче число може бути як з фіксованою точкою, так і в нормалізованому вигляді.
Приклад вхідного файлу
Приклад вихідного файлу
7
2 0
5 0
6 3.5
5 червня
4 лютого
7 березня
0 5
7 березня
7.5
В
Рішення . Можливо кілька різних підходів до вирішення даної задачі. Один з них - пошук найкоротшого шляху в графі (див. лекцію 8), в матриці суміжності якого записані відстані між вершинами кордону фонтану, якщо їх можна безпосередньо з'єднати шлангом і ВҐ, якщо цього зробити не можна. Для побудови такої матриці необхідно вміти перевіряти наявність перетину двох відрізків і у разі відсутності перетинів - місце розташування відрізка щодо кордону фонтану (всередині або зовні він знаходиться). У останньої подзадаче досить визначити місцезнаходження однієї з внутрішніх точок цього відрізка.
Знання різних геометричних формул було необхідно і при вирішенні завдання XIII Всеросійської олімпіади з інформатики "Пожежа" (див. [7]).
Висновок
Т.ч., в даній роботі ми розглянули елементарні підзадачі, на вирішення яких зазвичай спираються рішення задач обчислювальної геометрії, а також олімпіадні задачі, пов'язані з геометричними поняттями. У роботі наводяться докладні рішення завдань з коментарями і поясненнями. b>
Література
1. Препарату Ф. , Шеймос М. Обчислювальна геометрія: введення. - М.: Мир, 1989. p> 2. Окулов С.М. Геометричні алгоритми. "Інформатика", № 15, 16, 17, 2000. p> 3. Окулов С.М. 100 завдань з інформатики. Кіров: вид-во ВДПУ, 2000. p> 4. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритми. Побудова та аналіз. М.: МЦНМО, 2000. p> 5. Андрєєва Є., Фаліна І. Турбо-Паскаль у школі. М.: Изд-во Бочкарьової Н.Ф., 1998. p> 6. Станкевич А . С. Рішення завдань I Всеросійської командної олімпіади з програмування. "Інформатика", № 12, 2001. p> 7. Андрєєва Є.В. Рішення завдань XIII Всеросійської олімпіади з інформатики. "Інформатика", № 19, 2001. br/>
