| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 8 | 3 | 3 | 100.000% |
Farmer John has $N$ posts on his pasture. The pasture can be modeled as a coordinate plane where each post has integer coordinates.
John wants to connect the posts with wire segments that do not cross (in other words, the wire segments may only touch at their common endpoints) and form a number of triangular enclosures for his sheep. The sheep are fairly selfish, so each of them needs to be in a separate enclosure.
As the business is not going particularly well at the moment, John would like to use as litte wire as possible. Help him arrange the wire segments so that the total length of wire used is as small as possible, but he can accommodate the maximal number of sheep. John has a limited amount of wire and cannot use more than that.
The first line contains $N,ドル the number of posts on the pasture (3ドル \le N \le 10,000円$), and the integer $M,ドル the total length of wire that John has (1ドル \le M \le 10^{10}$). Each of the following $N$ lines contains two integers $X_i$ and $Y_i,ドル the coordinates of one fencepost ($-10^5 \le X_i, Y_i \le 10^5$). The posts are numbered 1ドル \ldots N$ in the order of their appearance in the input.
The first line should contain $K,ドル the number of wire segments, and $L,ドル the total length of wire spent. Each of the following $K$ lines should contain two integers $A$ and $B,ドル indicating that one of the wire segments should connect the posts $A$ and $B$. The total length of wire, $L,ドル should be given with exactly 6ドル$ decimal digits.
In this task you are given (via the grading server) 10ドル$ input files (input_001.txt to input_010.txt) and you should submit the corresponding output files (output_001.txt to output_010.txt) as your solution. You should not submit a program and it will not be graded.
A correct solution of a test case will get 10ドル \cdot \frac{M-C}{M-U}$ points, where $C$ is the length of wire spent in this solution and $U$ the length of wire spent in the best solution of this test case among all contestants (the latter may change during the contest and affect the score of each solution). This means points are given proportionally to the amount of wire saved.
A solution that does not respect the conditions of the task (the wire segments cross, the number of enclosures is not maximal, the claimed total length of wire $L$ does not agree with the layout of the segments, or more wire is spent than John actually has) will always score 0ドル$ points. It is known that John has enough wire for some solution in every test case.
4 19 0 0 0 3 3 0 4 3
5 17.404918 1 2 2 4 4 3 3 1 2 3
In this example, the posts are in the corners of a trapezoid and John has 19ドル$ units of wire. He can create two triangular enclosures, laying the wire segments on the edges of the trapezoid and on its shorter diagonal.
Another solution would be to lay the wire segments on the edges and the longer diagonal of the trapezoid. Then the total amount of wire used would be 18ドル.162278$. If contestants were to submit both solutions, those submitting the second solution would get 10ドル \cdot \frac{19-18.162278}{19-17.404918} \approx 5.25$ points.
Olympiad > Estonian Informatics Olympiad > 2021-22 > Open Competition 6-9번
Text