Боевой космический корабль «Рикенбакер» приближался к планете Оркут,
последнему оплоту враждебной расы шодан. Преимущество было на
стороне «Рикенбакера» — весь космический флот шодан уже был уничтожен.
Но тут поступили пугающие разведданные — на поверхности Оркута
было расположено несколько пусковых установок с ракетами класса «оркут-космос».
Все пусковые установки расположены на небольшом плоском плацдарме на
поверхности Оркута.
«Рикенбакер» оснащён дальнобойным лазером, способным
поразить пусковую установку раньше, чем корабль приблизится к планете на
опасное расстояние. С системой наведения лазера связана прямоугольная
декартова система координат. К сожалению, лазер может поразить только
такую цель, обе координаты которой в этой системе координат являются целыми.
Капитану «Рикенбакера» сообщили точные координаты каждой пусковой установки.
Теперь он хочет перед началом стрельбы один раз перенастроить лазер,
переместив начало системы координат в другую точку плоскости,
чтобы лазер смог поразить наибольшее число пусковых
установок. При этом капитан не может повернуть оси координат системы
наведения.
Помогите капитану выбрать точку, в которую нужно перенести начало
системы координат. Если существует несколько таких точек, выберите ту, расстояние
от которой до прежнего начала системы координат минимально.
Исходные данные
В первой строке записано целое число n (1 ≤ n ≤ 50 000) —
количество пусковых установок. В следующих n строках записаны
координаты этих установок — вещественные числа, не превосходящие
100 по абсолютной величине и имеющие не более трёх знаков после десятичной
точки. Координаты разных установок могут совпадать.
Результат
Выведите два числа — максимальное число установок, которое сможет уничтожить
лазер на «Рикенбакере», и минимальное расстояние, на которое потребуется
для этого перенести начало системы координат. Расстояние требуется вывести
с абсолютной погрешностью не более 10−5.
Примеры
исходные данные | результат |
---|
3
0.500 0.200
0.500 0.500
-0.500 0.200
| 2 0.53852
|
2
1.000 1.000
1.000 1.000
| 2 0.00000
|
Автор задачи: Виталий Белокобыльский, Сергей Маджуга
Источник задачи: Открытое личное первенство УрФУ по программированию 2012