Start

2018-04-04 05:00 AKDT

Set #11

End

2018-04-11 04:59 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1017 days 23:54:49

Time elapsed

167:59:59

Time remaining

0:00:00

Problem B
Closest Pair (Uniform)

Input

Input contains several test cases. Each test case begins with an integer $n$ ($2 \le n \le 100\, 000$). Then follows a list of $n$ points, one per line, each of the form $x$ $y$. Coordinates are floating point values with at most $2$ decimals and absolute value bounded by $100\, 000$. You may assume that the points have been generated by picking $x$ and $y$ independently uniformly at random in the interval $[-100\, 000, 100\, 000]$. The input is terminated by a case beginning with $0$.

Warning! This problem has a largish input file.

Output

For each test case, output any closest pair of the input points, on the form $x_{1}$ $y_{1}$ $x_{2}$ $y_{2}$.

Sample Input 1 Sample Output 1
2
1.12 0
0 0.51
3
158 12
123 15
1859 -1489
3
21.12 -884.2
18.18 43.34
21.12 -884.2
0
0.0 0.51 1.12 0.00
123 15 158 12.00
21.12 -884.20 21.12 -884.20