Recalling your youth, you remember spending long hours playing Sim City 1. 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.
Note: You can assume you can connect buildings directly with a straight-line path (unlike in the video game).
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-fa18-assignments # Go to assignments repository
$ git checkout master # Make sure we are on master
$ git pull --rebase # Pull any changes from GitLab
$ git checkout -b challenge17 # Create and checkout challenge17 branch
$ $EDITOR challenge17/program.cpp # Edit your code
$ git add challenge17/program.cpp # Stage your changes
$ git commit -m "challenge17: done" # Commit your changes
$ git push -u origin challenge17 # Send changes to GitLab
To check your code, you can use the .scripts/submit.py script or curl:
$ .scripts/submit.py
Submitting challenge17 assignment ...
Submitting challenge17 code ...
Result Success
Score 6.00
$ curl -F source=@challenge17/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa18/challenge17
{"score": 6, "result": "Success"}
Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 09 TA List to determine your corresponding TA for the merge request.
I was actually more of a fan of Sim Ant ↩
