Problem A
Treehouses
In a rainforest there are
Residents want easy transportation between all the treehouses and the open land, by some combination of walking (between those near the open land), and using one or more cables between treehouses. This may require the addition of more cables. Since the cables are expensive, they would like to add the smallest possible length of cable.
The height of a cable up two trees can be set so cables can criss-cross other cables, and not allow any snags or crashes. It is not safe to try to switch between two criss-crossed cables in mid-air!
Input
The input will start with the three integers
Next come
Next come
Output
The output is the minimum total length of new cable that
achieves the connection goal, expressed with absolute or
relative error less than
Sample Input 1 | Sample Output 1 |
---|---|
3 1 0 0.0 0.0 2.0 0.0 1.0 2.0 |
4.236067 |
Sample Input 2 | Sample Output 2 |
---|---|
3 1 1 0.0 0.0 0.5 2.0 2.5 2.0 1 2 |
2.000000 |
Sample Input 3 | Sample Output 3 |
---|---|
3 2 0 0.0 0.0 2.0 0.0 1.0 2.0 |
2.236067 |