Первый корабль с земными поселенцами высадился на Марсе. Колонисты успели возвести n необходимых построек на поверхности планеты (которую можно считать плоскостью, а постройки — точками на ней), но однажды сканеры поверхности зафиксировали подозрительную активность на подступах к колонии. Было решено воспользоваться системой генерации защитного силового поля, чтобы оградить колонию от возможных неприятностей.
Система работает следующим образом: на поверхности размещается некоторое количество генераторов поля (их тоже можно считать точками). Область действия каждого из генераторов представляет собой круг радиуса r с центром в точке расположения генератора (граница круга также входит в область). После включения системы силовым полем оказывается защищена только та часть поверхности, которая находится внутри области действия всех генераторов, то есть та часть, которая является пересечением областей действия генераторов.
Количество генераторов в распоряжении колонистов не ограничено, но система генерации поля потребляет много энергии. Более точно, потребляемая энергия не зависит от количества генераторов, но прямо пропорциональна площади, которая оказывается защищена полем. При этом необходимо, чтобы все имеющиеся постройки находились внутри защищенной области.
Определите минимально возможную площадь защищенной части поверхности, содержащей все постройки.
Выходные данные
Выведите одно вещественное число — минимальную площадь защищенной части, содержащей все постройки. Ответ принимается, если абсолютная либо относительная погрешность не превышает 10 - 4.
Примечание
В первом примере заданный радиус равен радиусу описанной окружности вокруг данных точек, поэтому соответствующий ей круг является искомой областью. Ответ — 25π.
Во втором примере область почти совпадает с квадратом с вершинами в данных точках.
Область для третьего примера изображена на рисунке ниже.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
0.00 0.000
0.0 8.00
6 8.00
|
78.5398163397
|
|
2
|
4 1000
0.0 0.0
0 2.00
2.00 2
2.0 0.00
|
4.0026666140
|
|
3
|
4 5
3.00 0.0
-3 0.00
0.000 1
0.0 -1.00
|
8.1750554397
|