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.
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.
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.
This is just a sample test case. There's no negative in the real test data.
Nice problem!!!Last edit: 2014-04-22 03:55:41
Omar Castaneda Infante:
Que quiere decir: el arbol se puede girar?