| Чемпионат КРОК 2016 - Отборочный Раунд |
|---|
| Закончено |
После того как гонка ядерных мууууружений завершилась, Фермер Джон и Бешеные Братья Беспорядка решили подписать мирное соглашение. Они договорились разделить территорию Бовинии прямой, проходящей хотя бы через два из n блокпостов, разбросанных по стране. Эти блокпосты, призраки прошлого конфликта, расположены в точках (x1, y1), (x2, y2), ..., (xn, yn).
Для того чтобы найти оптимальную линию раздела, Фермер Джон и Элси нарисовали карту Бовинии на координатной плоскости. Фермер Джон расположен в точке P = (a, 0), а Бешеные Братья Беспорядка окопались в точке Q = ( - a, 0). Поскольку они хотят, чтобы мир продолжался как можно дольше, решено было провести прямую, минимизирующую максимальную разницу между расстоянием от точек P и Q до какой-то точки на прямой.
Формально: определим разницу прямой 
по отношению к точкам P и Q как минимальное вещественное d,такое что для всех точек X прямой |PX - QX| ≤ d. Гарантируется, что такое d существует и единственно. Фермер Джон и Бесси хотят найти прямую, проходящую через какие-то два различных блокпоста (xi, yi) и (xj, yj), такую что разница этой прямой относительно точек P и Q минимальна.
В первой строке входных данных записаны два целых числа n и a (2 ≤ n ≤ 100 000, 1 ≤ a ≤ 10 000) — количество блокпостов и координаты фермы и базы соответственно.
В следующих n строках записаны целые координаты расположения блокпостов (xi, yi) (|xi|, |yi| ≤ 10 000). Гарантируется, что все блокпосты находятся в различных точках, не совпадающих с P и Q.
Выведите единственное число — минимально возможную разницу прямой относительно точек P и Q. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить 10 - 6.
А именно: пусть ваш ответ равен a, а ответ жюри — b. Проверяющая программа будет считать ваш ответ правильным, если 
.
2 5
1 0
2 1
7.2111025509
3 6
0 1
2 5
0 -3
0.0000000000
В первом примере возможна только прямая , задаваемая уравнением y = x - 1. Несложно заметить, что максимальное значение |PX - QX| достигается в точке X = (13, 12), 
, где 
.
Во втором примере, если провести прямую через точки (0, 1) и (0, - 3), получаем x = 0. PX = QX для всех её точек, поэтому ответ равен 0.
