350 200

200 200

1628

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

Задача 2 . На плоскости заданы N точек. Построить замкнутую ломаную без самопересечений и самокасаний, вершинами которой должны стать все заданные точки. (См., например, [5], аналогичная задача предлагалась на кировской областной олимпиаде 2002г. ).

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

2. Численное решение геометрических задач

В ряде случаев при решении геометрических задач формулы из вычислительной геометрии могут оказаться слишком громоздкими и приводят к решению нелинейных уравнений. Тогда на помощь могут прийти численные (приближенные) методы, позволяющие решить задачу за требуемое время и с нужной точностью. Такой подход был продемонстрирован в [6] при рассмотрении задачи “Фонтан” (ее не следует путать с задачей 6, приведенной ниже).

Из численных методов наиболее часто употребимым является метод дихотомии (деления пополам). Рассмотрим его на примере задачи XII Всероссийской олимпиады по информатике.

Задача 3 . Раздел царства.

Царство царя Гороха представляет собой выпуклый N -угольник, внутри которого расположены K селений. Царь решил завещать двум своим сыновьям по полцарства, одинаковые по площади и с равным количеством селений. Для этого он требует разделить царство одной прямолинейной границей.

Напишите программу, строящую границу согласно царской воле. Если граница проходит через селение, то оно может быть либо отнесено к одному из полуцарств, либо разделено на два селения, которые будут отнесены к разным полуцарствам (при нечетном K граница, естественно, должна разделить какое-то из селений).

Первая строка входного файла содержит количество вершин многоугольника N (3 N 50). В следующих N строках заданы координаты вершин многоугольника, перечисленные в порядке обхода контура по часовой стрелке. В (N +2)-ой строке указано количество селений K (0  K  100), а в последующих K строках заданы координаты селений. Все координаты — целые числа, не превосходящие по модулю 10⁶ . Размерами селений следует пренебречь.

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

Пример входного файла	Пример выходного файла
4 9 10 20 40 40 40 51 10 2 21 30 40 20	30.000000 35.000000 30.000000 15.000000

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

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

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

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

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

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