Świetliki
Limit pamięci: 128 MB
Z samego rana Bajtazar rozsiadł się wygodnie na pomoście przy Jeziorze Bajtockim
i oddał się swojemu ulubionemu hobby, czyli wędkowaniu.
W pewnym momencie zauważył, że nad spokojną taflą jeziora
unosi się wciąż wiele świetlików.
Widok ten spodobał się Bajtazarowi na tyle, że postanowił uwiecznić go na zdjęciu.
Zdjęcia robione aparatem Bajtazara mają kształt kwadratu.
Przed wykonaniem zdjęcia Bajtazar może ustawić aparat na dowolnej wysokości
i przesunąć go w lewo lub w prawo.
Nie chce go jednak obracać, żeby zdjęcie nie wyszło krzywe.
Aparat jest też wyposażony w funkcję zoom, służącą do przybliżania bądź oddalania
obrazu.
Bajtazar koniecznie chce, żeby wszystkie świetliki fruwające nad taflą jeziora
znalazły się na zdjęciu.
Za pomocą funkcji zoom chciałby ustawić parametry zdjęcia tak, żeby
owady miały na nim jak największe rozmiary.
Bajtazar jest skłonny trochę poczekać, aż ustawią się idealnie do zdjęcia.
Aby trochę uprościć sytuację, możemy założyć, że wszystkie
świetliki znajdują się cały czas w tej samej płaszczyźnie, równoległej do płaszczyzny matrycy aparatu,
oraz że każdy z nich porusza się ze stałym wektorem prędkości.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (),
oznaczającą liczbę świetlików.
Każdy z kolejnych wierszy zawiera cztery liczby całkowite , ,
, () oznaczające początkowe
położenie i wektor prędkości -tego owada.
Innymi słowy, po jednostkach czasu -ty świetlik znajdzie się w punkcie
.
Współrzędne punktów podane są w prostokątnym układzie współrzędnych, którego
osie są równoległe do boków matrycy aparatu.
Wyjście
Twój program powinien wypisać jeden wiersz zawierający nieujemną liczbę rzeczywistą
- minimalny bok kwadratu, którym można pokryć wszystkie świetliki w pewnym momencie czasu,
przy czym boki kwadratu muszą być równoległe do osi układu współrzędnych.
Wynik może różnić się od dokładnego o co najwyżej .
Przykład
Dla danych wejściowych:
4
4 0 -1 1
1 6 -1 -2
-1 -5 0 2
-1 -1 1 1
poprawną odpowiedzią jest:
3.00000000000000000000
Wyjaśnienie do przykładu: Na rysunku zaznaczono początkowe pozycje świetlików oraz
przebytą przez nie drogę w ciągu dwóch jednostek czasu. Zaznaczono też kwadrat o boku 3, który
zawiera wszystkie świetliki w chwili .