Square and Points
Time limit2sMemory limit128 MB
Given points inside a unit square with 4 fixed corners, find where to move the points to minimize the Steiner-tree-like minimum spanning length, then among those optimal configurations minimize total movement of points.
Problem
There are (N) points (P_1, P_2, \dots, P_N) in the unit square ([0,1] \times [0,1]). Points may lie on the boundary or at a corner.
Consider the four corners of the square and these (N) points as vertices. The length of an edge between two vertices is their Euclidean distance, and (Len(P)) is the minimum possible total edge length needed to connect all vertices.
You may move the given points to arbitrary positions in the square. Among all placements that minimize (Len), choose one that minimizes the total movement (\sum_{i=1}^{N} |P_i-Q_i|), where (Q_i) is the final position of the (i)-th point. Compute this minimum total movement.
Input
The input consists of several test cases. The first line of each test case contains the number of points (N), where (1 \le N \le 100).
Each of the next (N) lines contains the (x) and (y) coordinates of one point. Coordinates may be given with up to eight digits after the decimal point.
The input ends with a single line containing 0.
Output
For each test case, print the answer on its own line. An absolute or relative error of at most (10^{-3}) is accepted.
Hint
No additional hint is provided.