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:

  1. Consider points as vertices, segments as edges, it forms a rooted tree.
  2. Each node u is strictly higher than its parent, namely yu > yparent_of_u.
  3. 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:
sample1

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:
sample1
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

btw: either the second example or the input constraints are incorrect (they say x_i, y_i>=0 but the second testcase contains negative values)

Re: Sorry. Description modified.

Last edit: 2010-05-03 01:42:32
Omar Castaneda Infante: 2010-05-03 01:37:20

Que quiere decir: el arbol se puede girar?

Re: Yes. Please use English and read the description carefully.

Last edit: 2010-04-27 04:26:50

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