Balony

Limit pamięci: 64 MB

Organizatorzy CEOI 2011 zamierzają urządzić przyjęcie z mnóstwem balonów. Będzie ich , wszystkie w kształcie kuli, ułożone w jednym rzędzie na podłodze. Balony trzeba będzie napompować, na razie każdy z nich ma promień zero. Balon o numerze jest przymocowany do podłogi w punkcie o współrzędnej . Balony będą pompowane kolejno, od lewej do prawej. W czasie pompowania promień -tego balonu zwiększa się w sposób ciągły, aż do momentu kiedy osiągnie określoną dla niego górną granicę , lub balon dotknie któregoś z poprzednio napompowanych.

Balony z testu przykładowego, po pełnym napompowaniu.

Organizatorzy chcieliby wiedzieć, ile powietrza będzie potrzebne do napełnienia balonów. Twoim zadaniem jest wyznaczenie promienia, który osiągnie każdy z nich.

Wejście

Pierwszy wiersz standardowego wejścia zawiera liczbę całkowitą () - liczbę balonów. Kolejne wierszy opisuje balony: -ty z nich zawiera liczby całkowite oraz (, ). Możesz założyć, że balony są podane w kolejności rosnącej współrzędnej .

W testach wartych przynajmniej 40 punktów zachodzi dodatkowa nierówność .

Wyjście

Twój program powinien wypisać wierszy, przy czym -ty z nich powinien zawierać dokładnie jedną liczbę - promień -tego balonu po napełnieniu. Odpowiedź będzie zaakceptowana, jeśli każda liczba będzie różniła się od prawidłowej o co najwyżej .

Przykład

Dla danych wejściowych:

3
0 9
8 1
13 7

poprawną odpowiedzią jest:

9.000
1.000
4.694

Wskazówka: Aby wypisać wartość a typu long double z dokładnością do trzech miejsc po przecinku w C/C++, możesz użyć instrukcji printf("\%.3Lf\textbackslash n", a);. Aby wypisać to samo z użyciem strumieni w C++, użyj cout << fixed << setprecision(3); przed wypisaniem wartości za pomocą cout << a << "\textbackslash n"; (nie zapomnij dołączyć pliku nagłówkowego iomanip). W Pascalu możesz użyć instrukcji writeln(a:0:3);.

Zalecamy używanie typów long double w C/C++ oraz extended w Pascalu, ze względu na ich większą dokładność (w szczególności, przy ich użyciu żaden z rozważanych przez organizatorów poprawnych algorytmów nie miał problemów z błędami zaokrągleń).

Autor zadania: Jakub Pachocki.