| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 106 | 69 | 52 | 58.427% |
In a rainforest there are n treehouses high in the forest canopy on different trees (numbered from 1 to n). The i-th tree’s location is at (xi, yi). The first e of them in the list are close enough to neighboring open land around the rainforest so that transportation between all of them is easy by foot. Some treehouses may already be connected by direct straight cables through the air that can allow transport between them. 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!
The input will start with the three integers n (1 ≤ n ≤ 1 000), e (1 ≤ e ≤ n), and p (0 ≤ p ≤ 1 000), where p is the number of cables in place already.
Next come n lines, each with two real numbers x and y (|x|, |y| ≤ 10 000) giving the location of a treehouse. The i-th coordinate pair is for the treehouse with ID i. All coordinate pairs are unique. Real numbers are stated as integers or include one digit after a decimal point.
Next come p lines, each with two integers a, b, where 1 ≤ a < b ≤ n, giving the two treehouse ids of an existing cable between their trees. No ID pair will be repeated.
The output is the minimum total length of new cable that achieves the connection goal, expressed with absolute or relative error less than 0.001.
3 1 0 0.0 0.0 2.0 0.0 1.0 2.0
4.236
3 1 1 0.0 0.0 0.5 2.0 2.5 2.0 1 2
2.000
3 2 0 0.0 0.0 2.0 0.0 1.0 2.0
2.236