VNEMPIRE - Đế chế
English | Vietnamese |
An empire is building a network for its own planets. The empire consists of N planets, represented as points in the 3D space. The cost of connecting planet A and planet B is min{ |xA - xB|, |yA - yB|, |zA - zB| } with (xA, yA, zA), (xB, yB, zB) are coordinates of planet A, B in space. The empire is planning to build N - 1 connection and the requirement is that all planets are connected with each other and the cost is minimized.
Input
- Number of planets N (N < 100001).
- Next N lines, one line represents one coordiate of a planet.
Output
Only the minimum cost.
Example
Input 5 11 -15 -15 14 -5 -15 -1 -1 -5 10 -4 -1 19 -4 19 Output 4
Added by: | Trần Hải Đăng |
Date: | 2010-05-03 |
Time limit: | 0.400s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | COCI 2010 contest 7 |