A sensor network consists of a set of n sensors s₁, s₂,..., s_n. All the sensors are placed in a two dimensional plane and will never be moved again. Thus, each sensor s_i has a fixed coordinates (x_i, y_i).

A pair of sensors s_i and s_j can communicate by sending messages. Suppose that s_i wants to send a message directly to s_j, a fixed amount of electrical power p_{i, j} is required at s_i. In real world situation, the value of p_{i, j} depends on many factors. For simplicity we assume that the value of p_{i, j} depends only on the distance between the communicating sensors. In this problem, we assume that

Since the power stored in each sensor is a precious resource, sending message directly to the destination sensor may consume too much electrical power for a sensor. In this problem, we want to find an optimal path to send a message from s_i to s_j such that the maximum power required by the sensors on the path is minimized.

More formally, let P be a valid path from s_i to s_j. Let k₁ = i, k₂,..., k_r = j be the sequence of the indexes of the sensors along the path P. Define the weight of P by

w(P) = {p_{ki, ki+1}}.

Given a sensor network G, the sender s_i and the receiver s_j, write a program to compute an optimal path from s_i to s_j for sending a message.

Input 

An instance of the problem consists of

1. the number of sensors n,
2. the coordinates of the sensors (x_i, y_i), 1in, and
3. the source and the destination sensors s_i and t_i.

n/20 + 2

1. The first line is the integer n.
2. The following n/20 lines are the n coordinates (x_i, y_i), 1in. Each line contains at most 20 coordinates. Each coordinates is written in two numbers x_i and y_i, without the parentheses.
3. The last line of an instance contains two integer i and j, indicating s_i is the sender and s_j is the receiver.

0x_i, y_i < 2¹⁵

Note that the test data file may contain more than one instances. The last instance is followed by a line containing a single `0'.

Output 

The output for each test case is an integer w which is the maximum power required along the optimal path from s_i to s_j.

Sample Input 

4
0 0  1 9  8 2  10 10
1 4
5
0 0  8 2  3 4  8 7  10 10
1 5
0

Sample Output 

68
29

可以用 Dijkstra 或者是最小生成樹的想法去做, 這裡使用 Dijkstra

#include <iostream>
#include <cstdio>
#define oo 2147483647
using namespace std;

int Map[1000][1000];
int Max(int x, int y) {
    return x > y ? x : y;
}
int Min(int x, int y) {
    return x < y ? x : y;
}
int solve(int st, int ed, int n) {
    int i, j;
    int V[1000], Used[1000];
    for(i = 0; i < n; i++)
        V[i] = -oo, Used[i] = 0;
    V[st] = 0, Used[st] = 1;
    for(i = 0; i < n; i++) {
        int tn = st, next = oo;
        for(j = 0; j < n; j++)
            if(next > V[j] && V[j] != -oo && Used[j] == 0)
                next = V[j], tn = j;
        Used[tn] = 1;
        for(j = 0; j < n; j++) {
            if(V[j] != -oo)
                V[j] = Min(Max(V[tn], Map[tn][j]), V[j]);
            else
                V[j] = Max(V[tn], Map[tn][j]);
        }
    }
    return V[ed];
}
int main() {
    int n, X[1000], Y[1000], i, j;
    while(scanf("%d", &n) == 1 && n) {
        int st, ed;
        for(i = 0; i < n; i++)
            scanf("%d %d", &X[i], &Y[i]);
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                Map[i][j] = (X[i]-X[j])*(X[i]-X[j]) + (Y[i]-Y[j])*(Y[i]-Y[j]);
        scanf("%d %d", &st, &ed);
        printf("%d\n", solve(st-1, ed-1, n));
    }
    return 0;
}