Minimizing Maximum Distance in 2D Pairing

You are given an even number of points on a 2D plane. Your task is to pair these points into disjoint pairs such that the maximum Euclidean distance of any pair is minimized. The distance between two points ( (x_1, y_1) ) and ( (x_2, y_2) ) is given by [ d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} ] Compute and output the minimized maximum distance over all valid pairings.

Note: The number of points is small (e.g. ( N \le 14 )), and an exhaustive search using backtracking is an acceptable approach.

inputFormat

The input is read from standard input (stdin). The first line contains an even integer ( N ) (where ( 2 \le N \le 14 )) representing the number of points. Each of the following ( N ) lines contains two space-separated integers ( x ) and ( y ), which specify the coordinates of a point.

outputFormat

Output to standard output (stdout) a single line containing the minimized maximum distance, formatted to 9 decimal places.## sample

6
0 1
1 0
2 0
0 2
2 2
1 1

1.414213562