SEGTREE  Segment Tree
It was Arbor Day. Alice implemented an RBtree, Bob composed a segment tree, I made a binary tree  we all have a bright outlook.
Lambda is always making mistakes while implementing segment trees (See his history of submissions). He then decides to draw a "segment tree". He puts n points on a plane, link certain pairs of them to form segments and all the segments form a tree. As a normal tree, it satisfies the following conditions:
 Consider points as vertices, segments as edges, it forms a rooted tree.
 Each node u is strictly higher than its parent, namely y_{u} > y_{parent_of_u}.
 Segments may only intersect on their endpoints.
Lambda wants to minimize the total length of segments. The tree can be rotated to satisfy above conditions.
Input
First line of input contains single integer n (1 ≤ n ≤ 500).
Next n lines each contain two integers x_{i}, y_{i} denoting the coordinate of ith point (0 ≤ x_{i}, y_{i} ≤ 1000). Points are distinct.
Output
The one and only line contains a real number representing the minimum length.
Your answer must be rounded up to 4 digits after the decimal point.
Example 1
Input:
6
0 1
1 0
2 1
4 1
5 0
6 1
Output:
7.6569
Illustration:
Example 2
Input:
10
0 0
0 1
1 2
2 3
1 4
3 4
1 2
2 3
1 4
3 4
Output:
12.3137
Illustration:
This is just a sample test case. There's no negative in the real test data.
hide comments
Dragan MarkoviĆ¦:
20140415 23:23:02
Nice problem!!! Last edit: 20140422 03:55:41 

Sandro:
20100503 01:37:20
nice problem


Omar Castaneda Infante:
20100503 01:37:20
Que quiere decir: el arbol se puede girar?

Added by:  Lox 
Date:  20100427 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  Own problem. Description by Lambda 