Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: TN's Kingdom II - Construction
Description 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?
Input The input consists of a single test case. The first line of input contains a positive integer N not exceeding 10^{5} 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 L_{2}-metric, which means for two cities located at (x_{1}, y_{1}) and (x_{2}, y_{2}), the distance between them was
Output 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 2 0 0 1 1 Sample Output 1.4142 Hint It is recommended that your solution uses standard C I/O interface to achieve better efficiency and avoid unpredictable behaviours. Source POJ Monthly--2006.04.28, frkstyc@PKU_RPWT |

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

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator