Problem A
Closest Pair
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$. The input is terminated by a case beginning with $0$.
Warning! This problem has quite large input files.
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 |