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