问题描述

入门小白求解北京2004ACM的Square题

入门小白开始啃题，然而啃不动（无奈摊手）
求大神帮忙解答（最好是有解释啦）(?>ω<*?)
SquareTime Limit:?1000ms,?Special Time Limit:2500ms,?Memory Limit:32768KBTotal submit users:?177,?Accepted users:?26Problem 10002 :?No special judgementProblem descriptionGiven 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".

InputThe 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.?

OutputFor each test case, output the value of |P1P1"| + |P2P2"| + ... + |PNPN"|. The value should be rounded to three digits after the decimal point.

Sample Input1 0.2 0.5 2 0 0.5 0.5 0.5 0Sample Output0.300 0.500Judge Tips费马点

Problem SourceBeijing?2004

解决方案

http://www.cnblogs.com/rocketfan/archive/2009/05/20/1467236.html