Петр Васильевич в ярости! Ведь сосед Василий Петрович выгуливал козла в его
огороде! Как не предусмотрителен был Василий Петрович — ведь у Петра
Васильевича целых 2 козла и оба они в ответ будут поедать и вытаптывать
соседский огород.
Огород Василия Петровича большой и неогороженный, в некоторых его местах
растут деревья. Козлам потребуется много времени, чтобы выполнить свою
миссию. Поэтому Петр Васильевич решил привязать каждого козла к
какому-нибудь дереву, и пусть себе гуляют. Но привязать каждого надо так
чтобы он не доставал до всех деревьев кроме того, к которому он привязан,
иначе он запутается в веревке. Кроме того, надо чтобы они не доставали друг
до друга, иначе они будут вытаптывать одну и ту же территорию.
Чтобы нанести максимальный вред своему соседу, Петр Васильевич хочет, чтобы
суммарная площадь, доступная козлам была максимальна. Но нельзя привязывать
козла на расстоянии меньше 1 метра от дерева и дальше, чем на 50 метров.
Исходные данные
В первой строке записано целое число N (2 <= N <= 1000) —
количество деревьев в огороде. В следующих N строках записаны координаты
деревьев. Начало координат совмещено с центром огорода, координаты даны в
метрах с точностью до сантиметра. Координаты деревьев по модулю не
превосходят 100 метров. Можно считать, что нельзя привязать козла так, чтобы
он смог выйти за пределы огорода. Размерами самих козлов можно пренебречь.
Гарантируется, что козлов всегда можно привязать надлежащим образом.
Результат
Выведите максимальную площадь, которую смогут вытоптать козлы Петра
Васильевича, в м2 с точностью до 1 см2.
Пример
исходные данные | результат |
---|
8
1 1
-2 0
5 3
-2 3
8 3.10
-2 -1
-2 2
8 4.10
| 36.8060
|
Автор задачи: Владимир Яковлев
Источник задачи: XII командный чемпионат школьников Свердловской области по программированию (15 октября 2005 года)