[BOJ 8627] Żabka Bajtozja

View as PDF

Submit solution

Points: 2
Time limit: 1.0s
Memory limit: 512M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

Żabka Bajtozja siedzi sobie na jednym z kamieni wystających ponad powierzchnię stawu i chce wskoczyć do wody. Jednak nie jest jej obojętne, w jakim miejscu to uczyni. Otóż chciałaby zanurzyć się możliwie jak najdalej od miejsca, w którym się w tym momencie znajduje.</p>

Żabka jest jednak świadoma, że długość skoku, jaki może wykonać, jest ograniczona. Tak więc największa odległość, w jakiej mogłaby wskoczyć wody, byłaby równa właśnie długości jej najdłuższego skoku, gdyby nie wystające z wody kamienie. Bajtozja wpadła na pomysł, że może skakać po kamieniach, w ten sposób oddalić się i wskoczyć do wody w miejscu bardziej oddalonym od swojej początkowej pozycji. Pomóż jej i napisz program, który policzy, jak daleko od swojego aktualnego położenia żabka może się zanurzyć.

Napisz program, który:

  • wczyta ze standardowego wejścia opis położeń kamieni wystających ponad powierzchnię wody, umiejscowienie kamienia, na którym siedzi Bajtozja oraz długość maksymalnego skoku, jaki jest ona w stanie wykonać,
  • wyznaczy największą odległość, jaką żabka może przebyć z miejsca, w którym aktualnie siedzi, do miejsca, w którym zanurzy się pod wodę,
  • wypisze wynik na standardowe wyjście.
## 입력 형식

W pierwszym wierszu wejścia znajdują się trzy liczby całkowite $n$, $p$ oraz $s$ ($1 ≤ n ≤ 1\,000$, $1 ≤ p ≤ n$, $1 ≤ s ≤ 1\,000\,000\,000$), pooddzielane pojedynczymi odstępami i oznaczające odpowiednio: liczbę kamieni wystających ze stawu, numer kamienia, na którym siedzi Bajtozja oraz maksymalną długość skoku, jaki może ona wykonać, podaną w bajtymetrach.

W każdym z kolejnych $n$ wierszy znajdują się dwie liczby całkowite $x_i$ oraz $y_i$ ($-1\,000\,000\,000 ≤ x_i, y_i ≤ 1\,000\,000\,000$ dla $1 ≤ i ≤ n$), oddzielone pojedynczym odstępem i oznaczające współrzędne w bajtymetrach $i$-tego wystającego ze stawu kamienia.

출력 형식

Twój program powinien wypisać w pierwszym i jedynym wierszu wyjścia jedną liczbę, oznaczającą maksymalną odległość w bajtymetrach miejsca, w którym Bajtozja może się zanurzyć, od miejsca, w którym początkowo siedzi. Odległość tę należy wypisać z trzema cyframi po przecinku. Wypisana wartość może się różnić od dokładnej o co najwyżej $0.001$.

예제 입력

7 6 3
-3 0
2 1
2 -1
-6 -3
4 0
0 0
3 -1

예제 출력

7.000

힌트


Comments

There are no comments at the moment.