Hide

Problem D
Closest Pair

Input

Input contains several test cases. Each test case begins with an integer n (2n100000). 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 100000. 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 x1 y1 x2 y2.

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
Hide

Please log in to submit a solution to this problem

Log in