Zigzag#5795
Given several points on a plane, let us solve a puzzle by connecting them with a zigzag line. The goal is to find a zigzag line that passes through all the given points with the minimum number of turns. If there are multiple zigzag lines with the minimum number of turns, you should find the shortest one among them.
For example, consider the nine points shown in Figure 1.
Figure 1: The nine given points.
A zigzag line is composed of several straight line segments. Each segment must pass through two or more given points.
A zigzag line may turn at some of the given points, or anywhere else. Some points may be passed more than once.
Figure 2: Zigzag lines with three turning points.
Two zigzag lines with three turning points are depicted in Figure 2 (a) and (b) for the same set of given points shown in Figure 1. The length of the zigzag line in Figure 2 (a) is shorter than that in (b). In fact, the length of the zigzag line in Figure 2 (a) is the shortest, making it the solution for the nine points in Figure 1.
Another zigzag line with four turning points is illustrated in Figure 3. Its length is shorter than either line in Figure 2, but it has more turning points, so it is not the solution.
length = 10.0
Figure 3: A zigzag line with four turning points.
Consider another set of given points shown in Figure 4 (a) and (b) traversed by two zigzag lines.
Both lines have the same number of turning points, and the line in (a) is longer than in (b). However, (a) is the valid solution because one segment of the line in (b) passes through only one given point, which violates the rule.
Figure 4: Valid zigzag line with two turning points (a), and an invalid line (b).
Your task is to write a program to solve this puzzle.
The input consists of multiple datasets, each in the following format. The end of input is indicated by a line containing a single zero.
x_1 \ y_1
x_n \ y_n
All numbers in a dataset are non-negative integers, separated by a single space. is the number of given points. x_k and y_k (k = 1, \ldots, n) represent the coordinates of the -th point. The order of the points is irrelevant.
You may assume that 2 \leq n \leq 10, 0 \leq x_k \leq 10 and 0 \leq y_k \leq 10.
For each dataset, print two values: the minimum number of turning points and the length of the shortest zigzag line with that number of turning points, separated by a space. The length must be given as a decimal fraction with error less than (= 1.0 \times 10^{-4}).
You may assume that the minimum number of turning points is at most four, i.e., the number of line segments does not exceed five.
Sample solutions for the first four datasets in the sample input are illustrated in Figures 5 and 6.
Figure 5: Example solutions for the first and second datasets of the sample input.
Figure 6: Example solutions for the third and fourth datasets of the sample input.
Example 1