Minimizing the Diameter of Merged Fields

Farmer John owns several pastures (nodes) and some paths (edges) connecting them. A field is defined as a set of pastures that are connected (i.e. there exists a path between any two pastures in the set). Currently, there are at least two fields that are disconnected from each other. Farmer John plans to add exactly one new path connecting a pasture from one field to a pasture from another field. The weight of each edge is the Euclidean distance between the coordinates of the two pastures.

The diameter of a field is defined as the maximum over all pairs of pastures in that field of the shortest distance between them. Suppose that in one field the diameter is \( D_1 \) and in the other field the diameter is \( D_2 \). If we choose to connect pasture \( i \) (in the first field) and pasture \( j \) (in the second field), and let:

[ \delta(i,j) = \delta_i + d(i,j) + \delta_j, ]

where \( \delta_i \) is the maximum distance from pasture \( i \) to any other pasture in its field and \( d(i,j) \) is the Euclidean distance between pastures \( i \) and \( j \). Then the diameter of the new merged field is

[ \text{NewDiameter} = \max\Big( D_1,; D_2,; \delta_i + d(i,j) + \delta_j \Big). ]

Your task is to choose two pastures \( i \) and \( j \) (from two different fields) such that when they are connected, the diameter of the new merged field is minimized. Output the minimum possible diameter with 6 decimal places.

inputFormat

The input begins with an integer \(n\) (the number of pastures). Following that are \(n\) lines, each containing two numbers representing the \(x\) and \(y\) coordinates of a pasture. Then follow \(n\) lines each containing \(n\) numbers (each either 0 or 1) which form a symmetric adjacency matrix. If the \(j^{th}\) number in the \(i^{th}\) line is 1, then there is an existing path between pasture \(i\) and pasture \(j\) whose length is the Euclidean distance between them. It is guaranteed that there exist at least two fields (i.e. at least two connected components).

outputFormat

Output the minimum possible diameter of the new merged field after adding exactly one path connecting two pastures from different fields. The answer should be output with 6 decimal places.

sample

8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
0 1 0 0 0 0 0 0
1 0 1 1 1 0 0 0
0 1 0 0 1 0 0 0
0 1 0 0 1 0 0 0
0 1 1 1 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 0

12.07106