Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
TN's Kingdom II - Construction
Time Limit: 10000MSMemory Limit: 131072K
Total Submissions: 876Accepted: 115
Case Time Limit: 6000MS


It was the first anniversary of TN's coronation. After one year's reconstruction, towns and cities were gradually rebuilt. There emerged a call for a complete traffic system. Among all choices to solve the problem, TN considered the construction of an expressway system the best one. He followed his old way in planning - to build the fewest number of expressways that would connect all the cities.

Though it was a similar case to what had previously been done, differences existed. The most significant one was that building expressways was costly. TN wanted to minimize the cost to achieve the goal. It was known that the cost of building an expressway between two cities was proportional to the distance between the cities. What was more, the expressways were straight and no two expressways could cross each other due to technical limitations. Now TN was holding a map of his kingdom, fallen deep in thinking. How should he make the plan?


The input consists of a single test case. The first line of input contains a positive integer N not exceeding 105 which is the number of cities in the kingdom. Then N lines follow. Each line contains a pair of non-negative integers within 50,000, giving in that order the x- and y-coordinates of a city in the Cartesian coordinate system. The distance between two cities was measured in the L2-metric, which means for two cities located at (x1, y1) and (x2, y2), the distance between them was


Your solution should output a single number rounded to four decimal places which is the minimum cost of building the expressways under the assumption that building an expressway covering one unit of distance required exactly one unit of cost.

Sample Input

0 0
1 1

Sample Output



It is recommended that your solution uses standard C I/O interface to achieve better efficiency and avoid unpredictable behaviours.


POJ Monthly--2006.04.28, frkstyc@PKU_RPWT

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator