Cow Tours

Problem Background

Special for beginners, ^_^

Problem Description

Farmer John's farm has many pastures. Some paths connect particular pastures. A set of all pastures that are connected to each other is called a field. But for now, you can see that at least two pastures are disconnected. John wants to add one path on the farm (note: exactly one). This path is subject to the following restriction: the diameter of a field is the distance between the two farthest pastures in it (all distances mentioned in this problem refer to shortest distances). Consider the following two fields. Figure 1 shows a field with $5$ pastures; pastures are marked with *, and paths are drawn as straight lines. Each pasture has its own coordinates:

The diameter of the field shown in Figure 1 is about $12.07106$; the two farthest pastures are A and E, and the shortest path between them is A-B-E.

Both fields are on John's farm. John will choose one pasture from each of the two fields and connect them with a path so that, after connecting, this new, larger field has the smallest possible diameter. Note that if two paths intersect in the middle, we do not consider them connected. Only when two paths intersect at the same pasture do we consider them connected.

Now please write a program to find a path connecting two different fields such that, after adding this path, the new larger field has the smallest possible diameter.

Input Format

The first line: an integer $N$ ($1 \le N \le 150$), the number of pastures.

Lines $2$ to $N+1$: each line contains two integers $X, Y$ ($0 \le X, Y \le 100000$), the coordinates of the $N$ pastures. The coordinates of every pasture are distinct.

Lines $N+2$ to $2N+1$: each line contains $N$ numbers ($0$ or $1$) representing a symmetric adjacency matrix.

For example, the matrix descriptions of the two fields in the problem statement are as follows:

  A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0

The input data contains at least two disconnected pastures.

Output Format

A single line containing one real number: the answer sought. Keep six digits after the decimal point.

Sample Input

8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010

Sample Output

22.071068

Constraints

Time limit: 1s; memory limit: 1024 KiB for each test case.