Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024
Problem description
Firma Januszex S.A. zajmuje się aktualnie instalacją alarmów w biurowcach. Jasio jest pracownikiem firmy i wykonuje ostateczne sprawdzenie przygotowanej instalacji.
Na potrzeby tego zadania zakładamy, że biurowiec jest ograniczony prostymi x = 0 oraz x = W, wejście do biurowca jest na całej szerokości budynku w y = − ∞, a wyjście z biurowca jest na całej szerokości budynku w y = + ∞.
Alarm składa się z N czujek położonych w pewnych punktach. Każda czujka charakteryzuje się pozycją (współrzędne x oraz y) i zasięgiem r Przyjmujemy, że czujka wykryje dowolny obiekt, który znajdzie się choćby częściowo w jej zasięgu (tzn. w kole o promieniu r ze środkiem w punkcie (x,y)).
Zadaniem Jasia jest ustalić jak duży obiekt jest w stanie prześlizgnąć się przez budynek, przesunąć się z wejścia do wyjścia biurowca bez naruszenia czujki. Zakładamy tutaj, że obiekt jest kołem (należy ustalić promień największego koła spełniającego warunki zadania) i przesuwa się płynnie z idealną precyzją. Zakładamy też, że obiekt nie może dotykać ściany.
Oczywiście, jak to zwykle w takich zadaniach bywa, Jasio nie jest w stanie poradzić sobie sam i jak zawsze liczy na Twoją pomoc.
Napisz program, który: wczyta pozycje czujek oraz szerokość budynku, wyznaczy promień największego koła, które jest w stanie prześlizgnąć się przez budynek bez naruszenia czujek i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N oraz W, oddzielone pojedynczym odstępem. Oznaczają one kolejno: liczbę czujek oraz szerokość budynku. W kolejnych N wierszach znajduje się opis kolejnych czujek. Opis każdej z nich składa się z trzech liczb całkowitych xi, yi oraz ri określających kolejno: współrzędne punktu oraz zasięg i-tej czujki.
Dopuszczalne jest, żeby zasięg czujki wykraczał poza obrys budynku.
Wyjście
W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba rzeczywista – największy promień obiektu, który przemierzy budynek niezauważony.
Jeśli przejście budynku jest niemożliwe, należy wypisać 0.
Odpowiedź zostanie zaakceptowana jeśli będzie się różnić od poprawnej o nie więcej niż 10−6.
Ograniczenia
0 ≤ N ≤ 7 000, 1 ≤ W ≤ 100 000, − 100 000 ≤ xi, yi ≤ 100 000, 1 ≤ ri ≤ 100 000.
Przykład
| Input | Output | |
|
|