SEGTREE - Segment Tree
It was Arbor Day. Alice implemented an RB-tree, 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 yu > yparent_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 xi, yi denoting the coordinate of i-th point (0 ≤ xi, yi ≤ 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Ʀ:
2014-04-15 23:23:02
Nice problem!!! Last edit: 2014-04-22 03:55:41 |
|
Sandro:
2010-05-03 01:37:20
nice problem
|
|
Omar Castaneda Infante:
2010-05-03 01:37:20
Que quiere decir: el arbol se puede girar?
|
Added by: | Lox |
Date: | 2010-04-27 |
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 |