10088 - PE - Finding Bottleneck Shorstet Paths   

Status  |  Limits Submit

Description

 A sensor network consists of a set of n sensors s1, s2,..., sn. All the sensors are placed in a two dimensional plane and will never be moved again. Thus, each sensor si has a fixed coordinates (xi, yi).

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

 

pi, j = (xi - xj)2 + (yi - yj)2.

 

Furthermore, we assume that only the sender needs to consume this amount of power in the communication.

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 si to sj such that the maximum power required by the sensors on the path is minimized.

More formally, let P be a valid path from si to sj. Let k1 = i, k2,..., kr = j be the sequence of the indexes of the sensors along the path P. Define the weight of P by

 

w(P) = $displaystyle max_{{1le i<r}}^{}${pki, ki+1}.

 

A path P is an optimal path from si to sj if its weight w(P) is minimized among all paths from si to sj.

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

Input

An instance of the problem consists of

  1. the number of sensors n,
  2. the coordinates of the sensors (xi, yi), 1$ le$i$ le$n, and
  3. the source and the destination sensors si and ti.

These data are stored in $ lceil$n/20$ ceil$ + 2 lines in the input file.

  1. The first line is the integer n.
  2. The following $ lceil$n/20$ ceil$ lines are the n coordinates (xi, yi), 1$ le$i$ le$n. Each line contains at most 20 coordinates. Each coordinates is written in two numbers xi and yi, without the parentheses.
  3. The last line of an instance contains two integer i and j, indicating si is the sender and sj is the receiver.

In this problem, we assume that 1 < n < 1000, xi and yi are integers and 0$ le$xi, yi < 215.
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 si to sj. 

Sample Input  Download

Sample Output  Download

Tags




Discuss