P1265 Road Construction

There are $n$ cities in a country, and none of them are connected by roads, so travel is very inconvenient. To solve this "difficult travel" problem, the government decides to build roads. The construction task will be jointly completed by the cities. The construction proceeds in several rounds. In each round, each city selects the nearest city to it and applies to build a road to that city. The government reviews these applications to decide whether to approve construction. The government’s approval rules are as follows: 1. If two or more cities apply to build the same road, they will build it together. 2. If the roads applied for by three or more cities form a cycle, then, as shown below, A applies for road AB, B applies for road BC, and C applies for road CA. The government will deny the application for the shortest road among them. 3. All other applications are approved.  After a round of construction, some cities may become directly or indirectly connected by roads. These mutually reachable cities form a "city alliance". In the next round of construction, each "city alliance" is treated as a single city and acts as one. When all cities have been merged into a single "city alliance", the construction is complete. Your task is to compute the total length of the roads to be built, based on the city distribution and the rules above. #

The first line contains an integer $n$, the number of cities ($n \leq 5000$). Each of the following $n$ lines contains two integers $x$ and $y$, the coordinates of a city ($-10^6 \leq x, y \leq 10^6$). #

Output a real number, rounded to two decimal places, representing the total road length. (It is guaranteed that the answer is unique.) #

The roads to be built are shown in the figure:  Translated by ChatGPT 5