Problem A: Closest Pair of Points

CS F364 — Assignment 1

← Back to assignment

Problem

Given \(n\) points in a 2D plane, find the pair with the smallest Euclidean distance. A brute-force \(O(n^2)\) check of all pairs will not receive full credit.

Your program must output the minimum Euclidean distance (rounded to 6 decimal places) and the coordinates of the two closest points.

Input Format

• Line 1: integer \(n\) (\(2 \le n \le 10^5\))
• Lines 2 to \(n+1\): x y — floating-point coordinates. No two points coincide within the same input set.

Output Format

• Line 1: Euclidean distance of the closest pair, rounded to 6 decimal places.
• Line 2: x1 y1 x2 y2 — coordinates of the two closest points.

Tie-breaking

If multiple pairs share the same minimum distance, output the pair with the smallest \(x\)-coordinate for the first point (then smallest \(y\)), then the same for the second point.

Sample

Input

4
0.0 0.0
3.0 4.0
1.0 1.0
5.0 6.0

Output

1.414214
0.000000 0.000000 1.000000 1.000000

Explanation: Distances: (0,0)–(1,1) ≈ 1.414, (0,0)–(3,4) = 5, (0,0)–(5,6) ≈ 7.81, (1,1)–(3,4) ≈ 3.606, (1,1)–(5,6) ≈ 6.403, (3,4)–(5,6) ≈ 2.828. The closest is (0,0) and (1,1).

Download sample input