This page is still under construction.

Parts of this page are still being built. What you see may change.

Zigzag

Time limit3sMemory limit128 MB

Summary
Given up to 10 points on a small grid, find a polyline of collinear-point segments covering all points with the fewest bends, then minimal total length among such solutions.
Level

Medium7 of 10

Topics
Combinatorics, Geometry, Brute force, Backtracking
Solved
No attempts yet

Problem

Several points are given on a plane. We want to find a zigzag line that passes through all of them.

A zigzag line is a polyline made of several line segments joined end to end. It must satisfy the following rules.

  • Every segment of the zigzag line must pass through at least two of the given points.
  • Every given point must lie on the zigzag line; that is, each point must lie on at least one segment.

A point where the line bends is called a turning point. A turning point may or may not coincide with one of the given points. A zigzag line made of ss segments has s−1s - 1 turning points.

We look for a zigzag line that satisfies the following two conditions, in this order of priority.

  1. The number of turning points must be as small as possible.
  2. Among lines with the same number of turning points, the total length must be as small as possible.

The length of each segment is the Euclidean distance between its two endpoints, and the length of the zigzag line is the sum of the lengths of all its segments. Because every segment must pass through at least two points, a longer line can sometimes be the answer.

Given the points, write a program that computes the number of turning points and the length of such a zigzag line.

Input

The input consists of several test cases.

The first line of each test case contains the number of points nn. Each of the next nn lines contains the coordinates xx and yy of one point, separated by a space.

All coordinates are non-negative integers. nn is an integer with 2≤n≤102 \le n \le 10, and xx and yy are integers with 0≤x,y≤100 \le x, y \le 10. The order in which the points are given does not matter, and all points are distinct.

The last line contains 00, which marks the end of the input.

Output

For each test case, print on one line the number of turning points and the length of the shortest zigzag line among those with the fewest turning points, separated by a space.

Print the number of turning points as an integer, and print the length rounded to six decimal places.

The minimum number of turning points is at most 44, so the number of segments is at most 55.

Examples1

  1. Example 1

    Input
    2
0 0
10 9
4
0 0
3 1
0 3
3 3
10
2 2
4 2
6 2
2 4
4 4
6 4
2 6
4 6
6 6
3 3
10
0 0
2 0
4 0
0 2
2 2
4 2
0 4
2 4
4 4
6 8
9
0 0
1 0
3 0
0 1
1 1
3 1
0 2
1 2
2 2
10
0 0
1 0
0 1
1 1
9 9
9 10
10 9
10 10
0 2
10 8
10
0 0
0 10
2 0
2 1
2 7
2 10
5 1
6 7
9 2
10 9
0
    Expected output
    0 13.453624
1 18.486833
3 24.142136
4 24.948137
3 12.242641
3 60.782896
3 502.780435