| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 1 | 0 | 0 | 0.000% |
The astronomer has a passion for stargazing. In particular, he gets immense pleasure out of gazing at $k$ stars simultaneously through his telescope. Building a telescope with radius $r$ costs $t\cdot r$ kroner. A newly built telescope will point exactly at the origin $(0,0)$. Moving it to point somewhere else also takes effort; shifting the telescope a distance of $d$ units incurs a cost of $s\cdot d$ kroner. The astronomer can observe all stars at distance at most $r$ from where the telescope points.
How much does it cost to build and move a telescope that allows $k$ stars to be observed at once?
All coordinates and distances are given in the Euclidean plane.
Here is an example with $n=3$ stars at positions $(0,0)$, $(2,0)$, and $(3,1)$. The shaded area shows a telescope of radius $1$ pointing at $(1,0)$ covering two stars; this costs $s + t$ kroner and is an optimal solution to sample input $3$. The image also shows optimal solutions to sample inputs $1$, $2$, and $4$.
The first line consists of four integers: the number $k$ of stars the astronomer wants to observe, the number $n$ of stars in tonight's sky, the shifting cost $s$, and the telescope building cost $t$. Then follow $n$ lines, where the $i$th line contains the integer coordinates $x_i$ and $y_i$ of the $i$th star.
A single real number: the minimum number of kroner that the astronomer needs to spend.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 8 | $t\leq s$ |
| 2 | 9 | $n\le 50$ and $s=0$ |
| 3 | 18 | $s=0$ |
| 4 | 13 | $n\leq 50$ |
| 5 | 14 | $n\leq 350$ |
| 6 | 15 | $\epsilon = 1/10$ |
| 7 | 23 | No further constraints |
2 3 1000 500 0 0 2 0 3 1
1000.0
2 3 500 3000 0 0 2 0 3 1
3387.277541898787
2 3 250 750 0 0 2 0 3 1
1000.0
2 3 0 500 0 0 2 0 3 1
353.5533905932738
3 4 0 10 0 0 10 0 5 10 5 5
50.0