10016번 - Świetliki 스페셜 저지다국어

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.

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 100 000), oznaczającą liczbę świetlików. Każdy z kolejnych n wierszy zawiera cztery liczby całkowite x_i, y_i, a_i, b_i (-10⁶ ≤ x_i, y_i, a_i, b_i ≤ 10⁶) oznaczające początkowe położenie (x_i, y_i) i wektor prędkości [a_i, b_i] i-tego owada. Innymi słowy, po t jednostkach czasu i-ty świetlik znajdzie się w punkcie (x_i + t · a_i, y_i + t · b_i). 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.

Twój program powinien wypisać jeden wiersz zawierający nieujemną liczbę rzeczywistą d - 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 10^-3.

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 t = 2.