2

5.3 2.8 10.6 5.6 11.0 50.0

3.0 –4.0 –3.0 4.0 5.0 10.0

Встреча невозможна

3.0 -4.0 0.5

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

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

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

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

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

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

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

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

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

Примеры входного файла	Примеры выходного файла
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 строк — пара чисел через пробел, являющихся координатами вершин x ₁ y ₁ x ₂ y _{2 ¼} x_N y_N в порядке обхода ломаной против часовой стрелки, где 1, 2,..., N - номера вершин;

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

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

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

Пример входного файла	Пример выходного файла
7 2 0 5 0 6 3.5 5 6 4 2 « 1 2 3 4 5 6 » К-во Просмотров: 223 Бесплатно скачать Реферат: Геометрические задачи на олимпиадах по информатике >>> Скачать <<< Меню Поиск