Combat spaceship “Rickenbacker” was approaching planet Orkut, the last
citadel of the enemy race Shodan. “Rickenbacker” had all the advantage,
for the whole space force of Shodans had been already destroyed. But then
the frightening message came: there were several launching pads with
“Orkut-space” rockets on the surface of the planet. All the pads
were situated on the small military base on the surface of Orkut.
“Rickenbacker” is equipped with a long-range laser able to destroy the pad
before the spaceship enters the dangerous area around the planet. The
aiming system of the laser is bound to a rectangular Cartesian
system. Unfortunately, the laser can shoot at targets both coordinates
of which are integers.
Captain of “Rickenbacker” received the exact coordinates of every pad. Now
he wants to readjust the laser once before shooting by moving the
origin to another point on the surface so that the laser could
strike the largest amount of pads. The captain can’t rotate the
weapon aiming system.
Help the captain choose the new position of the origin.
If there are several such positions, choose the one
which is closest to the initial origin.
Input
The first line contains an integer n (1 ≤ n ≤ 50 000) that is
the number of the launching pads. The following n lines contain the
coordinates of these pads that are real numbers not exceeding 100 by
absolute value and are given with at most three digits after decimal point. Coordinates
of different pads may coincide.
Output
Output two numbers: the maximum amount of pads which Rickenbacker’s laser
can destroy and the minimum distance the origin needs to be
moved to. Absolute error of output distance shouldn't exceed
10−5.
Samples
input | output |
---|
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
|
Problem Author: Vitaliy Belokobilskiy, Sergey Madzhuga
Problem Source: Open Ural FU Personal Contest 2012