Challenge 17: Sim City

Recalling your youth, you remember spending long hours playing Sim City ¹. In this game you had the privilege and honor of building a city to your exact specifications and desires. You could build airports, sports stadiums, schools, industrial factories, residential homes, and more. It was your job to keep the citizens of your metropolis happy and prosperous.

Unfortunately, to pay for all of these construction projects, you had to tax your people. Even in the virtual world, people hate taxes and want you to spend their hard-earned income wisely. In particular, they would demand that you build roads to connect every building, but in the most cost efficient way.

Now that you have had some training in graph algorithms, you can easily tackle the problem of connecting every building in your city to every other building using the minimum amount of road. Given the coordinates of the buildings in a city, you are to connect them such that all buildings are reachable by road, while minimizing the amount of pavement you must lay down to make the connections.

Input¶

The input is a series of building locations specified by sets of point locations. The first line of a set denotes the number of points N, followed by N pair of points X Y. The end of the input is denoted when N = 0. N will never be larger than 100.

Example Input¶

3
1.0 1.0
2.0 2.0
2.0 4.0
0

Output¶

For each set of building locations, output the minimum total amount of road that must be constructed to connect all the buildings to two decimal places.

Example Output¶

3.41

Submission¶

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa21-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge17               # Create and checkout challenge17 branch

$ $EDITOR challenge17/program.py            # Edit your code

$ git add challenge17/program.py            # Stage your changes
$ git commit -m "challenge17: done"         # Commit your changes

$ git push -u origin challenge17            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

$ .scripts/check.py
Checking challenge17 program.py ...
  Result Success
    Time 0.02
   Score 6.00 / 6.00

$ curl -F source=@challenge17/program.py https://dredd.h4x0r.space/code/cse-30872-fa21/challenge17
{"result": "Success", "score": 6, "time": 0.01631760597229004}