| Турнир Архимеда 2021 |
|---|
| Закончено |
Агроном Больжедор десять лет не посещал свой участок. Представим, что он (участок) имеет форму бесконечной плоскости и за это время зарос сорной травой. Больжедор хочет сжечь как можно больше травы, потратив на это как можно меньше сил и времени.
На поле есть $$$n$$$ электрических столбов. Один из способов избавиться от травы заключается в том, что можно выбрать два столба и вызвать между ними электрический разряд. Электроэнергии у Больжедора не очень много, поэтому можно вызвать только один разряд между одной парой столбов. От этого загорится отрезок травы между столбами. После этого огонь будет распространяться с постоянной скоростью $$$v$$$ метров в минуту, а именно, если рассмотреть моменты $$$T_0$$$ и $$$T_1=T_0+t$$$ (где $$$t$$$ — время в минутах), то точка $$$X$$$ будет гореть в момент $$$T_1$$$ тогда и только тогда, когда есть точка $$$Y$$$, горевшая в момент $$$T_0$$$, для которой длина отрезка $$$XY$$$ не больше $$$vt$$$.
Есть одна проблема: по прогнозу через $$$H$$$ часов пойдёт дождь и затушит всю траву. Найдите наибольшую площадь травы, которую Больжедору удастся сжечь с помощью электрических столбов.
Первая строка содержит три целых числа, разделенных пробелами: $$$n$$$ — количество столбов, $$$H$$$ — время до начала дождя в часах и $$$v$$$ — скорость распространения огня в метрах в минуту ($$$2 \leqslant n \leqslant 100$$$; $$$1 \leqslant H \leqslant 12$$$; $$$1 \leqslant v \leqslant 100$$$).
Каждая из следующих $$$n$$$ строк содержит по два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты $$$i$$$-го столба в метрах ($$$-10000 \leqslant x_y,y_i \leqslant 10000$$$). Гарантируется, что положения всех $$$n$$$ столбов различны.
Выведите одно вещественное число — наибольшую площадь травы, которую удастся сжечь, в квадратных метрах.
Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превосходит $$$10^{-6}$$$. А именно, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет засчитан, если $$$\frac{|a-b|}{\max(1,b)} \leqslant 10^{-6}$$$.
3 2 1 1 0 -1 1 0 0
45775.59052629
| Название |
|---|


