Problem A
Astronom
Languages
da
de
en
fi
lt
lv
pl
uk
Pasją pewnego astronoma jest obserwacja gwiazd. W szczególności czerpie on ogromną przyjemność z wpatrywania się w $k$ gwiazd jednocześnie przez swój teleskop. Budowa teleskopu o promieniu $r$ kosztuje $t\cdot r$ koron. Nowo zbudowany teleskop będzie wskazywał dokładnie na początek $(0,0)$. Przesuwanie go tak, by wskazywał gdzie indziej, również wymaga wysiłku; przesunięcie teleskopu o odległość $d$ jednostek kosztuje $s\cdot d$ koron. Astronom może obserwować wszystkie gwiazdy w odległości co najwyżej $r$ od miejsca, na które wskazuje teleskop.
Ile kosztuje zbudowanie i przesunięcie teleskopu, który umożliwia jednoczesną obserwację $k$ gwiazd?
Wszystkie współrzędne i odległości podane są w płaszczyźnie euklidesowej.
Przykład
Oto przykład z $n=3$ gwiazdami na pozycjach $(0,0)$, $(2,0)$ oraz $(3,1)$. Zacieniowany obszar pokazuje teleskop o promieniu $1$ skierowany na $(1,0)$ obejmujący dwie gwiazdy; kosztuje to $s + t$ koron i jest optymalnym rozwiązaniem dla przykładowego wejścia $3$. Obraz pokazuje również optymalne rozwiązania dla przykładowych wejść $1$, $2$ oraz $4$.
![\includegraphics[width=.3\textwidth ]{img/samples.pdf}](/problems/astronomer/file/statement/pl/img-0002.png)
Wejście
Pierwszy wiersz składa się z czterech liczb całkowitych: liczba $k$ gwiazd, które astronom chce obserwować, liczba $n$ gwiazd na dzisiejszym niebie, koszt przesunięcia $s$, oraz koszt budowy teleskopu $t$. Następnie znajduje się $n$ wierszy, gdzie $i$-ty wiersz zawiera współrzędne całkowite $x_ i$ oraz $y_ i$ gwiazdy o numerze $i$.
Wyjście
Pojedyncza liczba rzeczywista: minimalna liczba koron, którą astronom musi wydać.
Ograniczenia i punktacja
Możesz założyć
-
$1\leq k\leq n\leq 700$.
-
$x_ i, y_ i\in \{ -10^9,\ldots , 10^9\} $ dla każdego $i\in \{ 1,\ldots ,n\} $.
-
$s,t\in \{ 0,\ldots , 10^9\} $.
-
Twoja odpowiedź będzie zaakceptowana, jeśli mieści się w względnej lub bezwzględnej tolerancji $\epsilon = 10^{-6}$ od prawidłowej odpowiedzi.
Twoje rozwiązanie zostanie przetestowane na zestawie grup testowych, z których każda jest warta pewną liczbę punktów. Każda grupa testowa zawiera zestaw przypadków testowych. Aby uzyskać punkty za grupę testową musisz rozwiązać wszystkie przypadki testowe w tej grupie. Twój ostateczny wynik będzie maksymalnym wynikiem pojedynczego zgłoszenia.
|
Grupa |
Punkty |
Ograniczenia |
|
$1$ |
$8$ |
$t\leq s$ |
|
$2$ |
$9$ |
$n\le 50$ oraz $s=0$ |
|
$3$ |
$18$ |
$s=0$ |
|
$4$ |
$13$ |
$n\leq 50$ |
|
$5$ |
$14$ |
$n\leq 350$ |
|
$6$ |
$15$ |
$\epsilon = 1/10$ |
|
$7$ |
$23$ |
Brak dodatkowych ograniczeń |
| 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 |
