Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_06_06 - Ogród Jasia |
Ogród Jasia
Jasiu ma piękny ogród pełen różnokolorowych kwiatów, które do tej pory podlewał konewką. Postanowił, że zakupi jeden zraszacz i umiejscowi go w miejscu, gdzie swoim zasięgiem będzie obejmował jak najwięcej kwiatów. Metodą prób i błędów próbował znaleźć takie miejsce, ale nie jest pewien, czy nie można zrobić tego lepiej. Gdyby chociaż wiedział jaką największą liczbę kwiatów może podlewać jego zraszacz, wtedy na pewno udało by mu się znaleźć takie miejsce.
Znając współrzędne wszystkich kwiatów w ogrodzie oraz promień zasięgu działania zraszacza, wyznacz największą liczbę kwiatów, jaką będzie mógł ów zraszacz podlewać.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n, r (2 ≤ n < 1000, 1 ≤ r < 104), gdzie n to liczba kwiatów w ogrodzie, a r to promień zasięgu działania zraszacza.
Dalej w n wierszach podane są współrzędne kwiatów, w każdym wierszu dwie liczby całkowite x, y (-104 < x, y < 104).
Należy założyć, że żadne dwa kwiaty nie rosną w tym samym miejscu.
Wyjście
Na wyjściu należy podać największą liczbę kwiatów, które może nawadniać zraszacz.
Uwaga: zraszacz umiejscowiony w punkcie oddalonym od pewnego kwiatka dokładnie o odległość promienia, będzie nawadniał ten kwiatek i Jasiu już nie musi się trudzić podlewać go konewką.
Przykład
Wejście
14 3
1 3
1 4
2 2
3 1
6 1
7 2
2 5
3 6
4 4
5 3
6 6
7 5
8 3
8 4
Wyjście
10
Rysunek do przykładu. Czarny punkt to optymalne miejsce dla zraszacza, który nawadniał będzie 10 z 14 kwiatów.
Dodane przez: | Mariusz Śliwiński |
Data dodania: | 2013-05-01 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 GOSU |
Pochodzenie: | ALGOLIGA |