Problem A
Tähtitieteilijä
Languages
da
de
en
fi
lt
lv
pl
uk
Tähtitieteilijä on intohimoinen tähtien tarkkailija. Tarkemmin ottaen, häntä miellyttää erityisesti $k$:n tähden samanaikainen katselu teleskoopinsa avulla. $r$-säteisen teleskoopin rakentaminen maksaa $t\cdot r$ kruunua. Rakentamisen jälkeen teleskooppi osoittaa tarkalleen origoon $(0,0)$. Sen suuntaaminen muualle on työlästä; $d$:n yksikön siirros maksaa $s\cdot d$ kruunua. Tähtitieteilijä voi tutkia teleskoopilla kaikkia tähtiä, joiden etäisyys teleskoopin osoittamasta pisteestä on enintään $r$.
Kuinka paljon maksaa rakentaa ja suunnata teleskooppi, jonka avulla voi tutkia $k$:ta tähteä samanaikaisesti?
Kaikki koordinaatit ja etäisyydet annetaan euklidisessa tasossa.
Esimerkki
Tässä esimerkissä $n=3$ tähteä sijaitsee pisteissä $(0,0)$, $(2,0)$ ja $(3,1)$. Väritetty alue näyttää $1$-säteisen teleskoopin, joka osoittaa pisteeseen $(1,0)$ peittäen kaksi tähdistä; tämä maksaa $s + t$ kruunua ja on optimaalinen ratkaisu esimerkkisyötteeseen $3$. Kuvassa näkyy myös optimaalinen ratkaisu esimerkkisyötteisiin $1$, $2$ ja $4$.
![\includegraphics[width=.3\textwidth ]{img/samples.pdf}](/problems/astronomer/file/statement/fi/img-0002.png)
Syöte
Ensimmäisellä rivillä on neljä kokonaislukua: määrä tähtiä $k$, joita tähtitieteilijä haluaa tutkia samanaikaisesti, tähtien määrä yön taivaalla $n$, siirtohinta $s$ ja teleskoopin rakennushinta $t$. Seuraa $n$ riviä, joista $i$:s sisältää $i$:nnen tähden kokonaislukukoordinaatit $x_ i$ ja $y_ i$.
Tuloste
Yksi reaaliluku: pienin määrä kruunuja, joka tähtitieteilijän tulee käyttää.
Rajoitukset ja pisteytys
Voit olettaa, että
-
$1\leq k\leq n\leq 700$.
-
$x_ i, y_ i\in \{ -10^9,\ldots , 10^9\} $ kaikille $i\in \{ 1,\ldots ,n\} $.
-
$s,t\in \{ 0,\ldots , 10^9\} $.
-
vastauksesi hyväksytään, jos sen suhteellinen tai absoluuttinen virhe on korkeintaan $\epsilon = 10^{-6}$ oikeaan vastaukseen nähden.
Ratkaisu testataan testiryhmillä, joista kullakin on oma pistemäärä. Jokainen testiryhmä sisältää joukon testitapauksia. Ryhmän pisteet saa vain, jos ratkaisee kaikki sen testitapaukset. Tehtävän lopullinen pistemäärä on suurin yksittäisen lähetyksen pistemäärä.
|
Ryhmä |
Pisteet |
Rajoitukset |
|
$1$ |
$8$ |
$t\leq s$ |
|
$2$ |
$9$ |
$n\le 50$ ja $s=0$ |
|
$3$ |
$18$ |
$s=0$ |
|
$4$ |
$13$ |
$n\leq 50$ |
|
$5$ |
$14$ |
$n\leq 350$ |
|
$6$ |
$15$ |
$\epsilon = 1/10$ |
|
$7$ |
$23$ |
Ei muita rajoituksia |
| Sample Input 1 | Sample Output 1 |
|---|---|
2 3 1000 500 0 0 2 0 3 1 |
1000.0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 3 500 3000 0 0 2 0 3 1 |
3387.277541898787 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 3 250 750 0 0 2 0 3 1 |
1000.0 |
| Sample Input 4 | Sample Output 4 |
|---|---|
2 3 0 500 0 0 2 0 3 1 |
353.5533905932738 |
| Sample Input 5 | Sample Output 5 |
|---|---|
3 4 0 10 0 0 10 0 5 10 5 5 |
50.0 |
