B1 - Balóny

Časový limit: 4s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Na programátorských súťažiach sa zaužívalo pre zvýšenie atraktivity počas riešenia praktických úloh označenie vyriešenia úlohy prilepením balónu (každá úloha má svoju vlastnú farbu). Takže pozorovatelia v miestnosti vidia, kto má najviac balónov (a teda najviac vyriešených úloh).

Organizátori celoštátneho kola Olympiády v informatike (ktoré sa tohto roku konalo v Košiciach) sa zamýšľali nad podobným spestrením riešenia praktického dňa. Systém hodnotenia je v tejto súťaži odlišný - hodnotí sa až posledné riešenie a je možné za neho dostať niekoľko bodov (podľa toho, koľko testovacích vstupov vyrieši správne). Čím je algoritmus efektívnejší, tým získa viac bodov. Rozhodli sa teda, že budú balóny nafúkavať za každé poslané riešenie. Umiestňovať ich budú zaradom na vopred určené pozície (na jednu dlhú poličku). Každý balón (v tvare gule) nafúknu do polomeru určeného počtom bodov, pričom ale nafukovanie prerušia hneď, ako sa balón dotkne niektorého z už nafúknutých balónov. Pomôžte im určiť ako silno musia nafúknuť každý balón, pričom ich budú nafukovať v poradí zľava doprava.

Úloha

Daný je zoznam umiestnenia balónov spolu s prislúchajúcimi počtami bodov (maximálne polomery balónov), ktoré chce komisia umiestniť. Pre každý balón vypočítajte, ako ho možno čo najviac nafúknuť tak, aby ho bolo možné umiestniť k už doteraz položeným balónom.

Vstup

Prvý riadok vstupu obsahuje jedno kladné celé číslo N, počet balónov. Nasledujúcich N riadkov obsahuje po dve celé čísla pre každý balón - pozíciu X_i (0 ≤ X_i ≤ 10⁹) a požadovaný polomer R_i (0 ≤ R_i ≤ 10⁹). Môžete predpokladať, že balóny sú zadané zľava doprava, teda podľa rastúcej súradnice (X).

B1

1 ≤ N ≤ 2 000

B2

1 ≤ N ≤ 200 000

Výstup

Výstupom je N riadkov vypisujúcich polomery maximálne nafúkaných balónov s presnosťou na (aspoň) 3 desatinné miesta (akceptované sú riešenia, ktoré sa líšia najviac o 0.001).

Príklad

Vstup:

Výstup:

15.000
1.000
4.817

Upozornenie

Nezabudnite na rozsahy hodnôt, teda používajte dostatočné veľké a presné číselné typy - (Pascal: Longint / Extended, C++ a Java: long / double).

Na výpis hodnôt môžete použiť:
Pascal: Writeln(r:0:4);
C++: printf("%0.4f\n", r);
Java: System.out.printf("%.4f\n", r);

UPJŠ ŠVK 2013