Геометрические задачи на олимпиадах по информатике

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· в каждой из последующих N строк — пара чисел через пробел, являющихся координатами вершин x1 y1 x2 y2 ¼ xN yN в порядке обхода ломаной против часовой стрелки, где 1, 2, ., N - номера вершин;

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

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

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

 Скачать реферат