Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Square
Description Given a square at [0, 1] * [0, 1] that has N points ( P _{1}, P_{2}, ..., P_{N} ) in the square (you may assume that different points can be at the same position), we can connect the N points and the four corners of the square with some line segments so that through these segments any two of the N+4 points can reach each other (directly or indirectly). The graph length is defined as the total length of the line segments. When N points' positions are fixed, there must exist a way of connecting them, such that it will make the shortest graph length. We can use LEN (P_{1}, P_{2}, ..., P_{N}) to record the graph length using this way of connecting.
In this situation, LEN (P _{1}, P_{2}, ..., P_{N}) is a function of P_{1}, P_{2}, ..., P_{N}. When P_{1}, P_{2}, ..., P_{N} change their positions, LEN (P_{1}, P_{2}, ..., P_{N}) also changes. It's easy to prove that there exist some P_{1}', P_{2}', ..., P_{N}' in the square such that LEN (P_{1}', P_{2}', ..., P_{N}') is at its minimum.
Given the initial positions of N points, your task is to find out N points P _{1}", P_{2}", ..., P_{N}" in the square such that |P_{1}P_{1}"| + |P_{2}P_{2}"| + ... + |P_{N}P_{N}"| is minimum and LEN (P_{1}", P_{2}", ..., P_{N}") = LEN (P_{1}', P_{2}', ..., P_{N}') . You are requested to output the value of |P_{1}P_{1}"| + |P_{2}P_{2}"| + ... + |P_{N}P_{N}"|, where |PiPi"| is the distance between Pi and Pi".
For example, Figure-1 gives the initial position of P _{1} and the way of connecting to obtain LEN (P_{1}). In Figure-2, it gives the position of P_{1}", which is at the center of the square, and the way of connecting to obtain LEN (P_{1}"). It can be proved that LEN (P_{1}") = LEN (P_{1}’); your job is to output the distance between P_{1} and P_{1}".Input The input consists of several test cases. For each test case, the first line consists of one integer N (1 <= N <= 100), the number of points, and N lines follow to give the coordinates for every point in the following format:
x y Here, x and y are float numbers within the value [0, 1]. A test case of N = 0 indicates the end of input, and should not be processed. Output For each test case, output the value of |P _{1}P_{1}"| + |P_{2}P_{2}"| + ... + |P_{N}P_{N}"|. The value should be rounded to three digits after the decimal point.Sample Input 1 0.2 0.5 2 0 0.5 0.5 0.5 0 Sample Output 0.300 0.500 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator