Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Square
Time Limit: 1000MSMemory Limit: 30000K
Total Submissions: 912Accepted: 238

Description

Given a square at [0, 1] * [0, 1] that has N points ( P1, P2, ..., PN ) 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 (P1, P2, ..., PN) to record the graph length using this way of connecting.

In this situation, LEN (P1, P2, ..., PN) is a function of P1, P2, ..., PN. When P1, P2, ..., PN change their positions, LEN (P1, P2, ..., PN) also changes. It's easy to prove that there exist some P1', P2', ..., PN' in the square such that LEN (P1', P2', ..., PN') is at its minimum.

Given the initial positions of N points, your task is to find out N points P1", P2", ..., PN" in the square such that |P1P1"| + |P2P2"| + ... + |PNPN"| is minimum and LEN (P1", P2", ..., PN") = LEN (P1', P2', ..., PN') . You are requested to output the value of |P1P1"| + |P2P2"| + ... + |PNPN"|, where |PiPi"| is the distance between Pi and Pi".

For example, Figure-1 gives the initial position of P1 and the way of connecting to obtain LEN (P1). In Figure-2, it gives the position of P1", which is at the center of the square, and the way of connecting to obtain LEN (P1"). It can be proved that LEN (P1") = LEN (P1’); your job is to output the distance between P1 and P1".

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 |P1P1"| + |P2P2"| + ... + |PNPN"|. 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]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator