LINE - Connect Line Segments

Your dear son Arnie is addicted to a puzzle named Connect Line Segments.

In this puzzle, you are given several line segments placed on a two-dimensional area. You are allowed to add some new line segments each connecting the end points of two existing line segments. The objective is to form a single polyline, by connecting all given line segments, as short as possible. The resulting polyline is allowed to intersect itself.

Arnie has solved many instances by his own way, but he is wondering if his solutions are the best one. He knows you are a good programmer, so he asked you to write a computer program with which he can verify his solutions.

Please respond to your dear Arnie’s request.

Input

The input consists of multiple test cases.

Each test case begins with a line containing a single integer n (2 ≤ n ≤ 14), which is the number of the initial line segments. The following n lines are the description of the line segments. The i-th line consists of four real numbers: xi,1, yi,1, xi,2, and yi,2 (-100 ≤ xi,1, yi,1, xi,2, yi,2 ≤ 100). (xi,1, yi,1) and (xi,2, yi,2) are the coordinates of the end points of the i-th line segment.

The end of the input is indicated by a line with single "0".

Output

For each test case, output the case number followed by the minimum length in a line.

The output value should be printed with five digits after the decimal point.

Example

Input:
4
0 1 0 9
10 1 10 9
1 0 9 0
1 10 9 10
2
1.2 3.4 5.6 7.8
5.6 3.4 1.2 7.8
0

Output:
Case 1: 36.24264
Case 2: 16.84508

Added by:Bin Jin
Date:2008-09-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:JAG wintercamp 08, day2

hide comments
2020-05-11 09:55:05
@atanu chakraborty, My accepted solution took 0.3sec here and stress testing locally shows me that I can run up to 30 test cases (each with n = 14) within 1 sec. So it has to be a lot less than 30.
2015-03-04 11:38:11 atanu chakraborty
constraint on number of test cases?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.