Niektorý KSP-áci1 práve končia magisterské štúdium. Už len tento fakt je celkom šialená jazda. Medzi týmito KSP-ákmi je aj Jaro. Jaro teraz každý večer poctivo trávi na farme (serverovej) a počíta kaktusy. Dáva to zmysel? (Ne)bojte sa, po piatich rokoch vysokej školy bude.
Jaro už má toho všetkého dosť a rozhodol sa, že si pôjde vyvetrať hlavu. Normálny človek by išiel na futbal alebo na kofolu, Jaro sa ale rozhodol, že sa pôjde prevetrať na kolotoč. Ako nástroj svojho plánu si zvolil ruské kolo.
Na zľavomate vyhrabal kupón a už aj stál pred kolotočom. Hneď aj pochopil, prečo bola na tento kolotoč taká veľká zľava. Konštrukciu mal hrdzavú, farbu opadanú, otáčal sa podozrivo rýchlo, a ešte aj kabínky mal povešané kade-tade.
Jaro si teraz musí jednu z týchto kabíniek vybrať.
Jeho mentálne sily sú už ale na dne a chcel by vás poprosiť o pomoc.
Úloha
Celú situáciu si môžeme predstaviť v dvoch rozmeroch (výška a šírka). Každá kabínka sa na začiatku nachádza v nejakom bode roviny. Kolotoč sa otáča rovnomerným otáčavým pohybom okolo stredu, ktorý je v bode \([0,0]\). Jaro by si chcel vybrať kabínku, v ktorej sa bude najdlhšie cítiť nad vecou, t. j. takú, ktorá bude počas jednej otáčky kolotoča najdlhší čas vyššie ako všetky ostatné kabínky. Zistite, ktorá to je!
Formát vstupu
V prvom riadku je číslo \(n\), \((1 \leq n \leq 10^6)\) – počet kabíniek na kolotoči. Nasleduje \(n\) riadkov, \(i\)-ty z nich obsahuje čísla \(x_i\) \(y_i\) (\(-10^5 \leq x_i, y_i \leq 10^5\)) – súradnice \(i\)-tej kabínky. Môžete predpokladať, že žiadne dve kabínky nemajú rovnaké súradnice a všetky súradnice sú celočíselné.
Formát výstupu
Vypíšte súradnice najlepšej kabínky. Ak je takých viac, vyberte tú s najmenšou \(x\)-ovou súradnicou. Ak je aj takých viac, vyberte tú s najmenšou \(y\)-ovou súradnicou.
Hodnotenie
Pre jednotlivé testovacie sady platia nasledujúce obmedzenia:
číslo sady | \(1\) | \(2\) | \(3\) | \(4\) |
---|---|---|---|---|
\(n \leq\) | \(10^3\) | \(10^4\) | \(10^5\) | \(10^6\) |
Príklady
Input:
5
-1 -1
1 -1
-1 1
1 1
0 0
Output:
-1 -1
Na vstupe je štvorec, každá kabínka bude najvyššie štvrtinu času, okrem strednej, ktorá bude vždy v strede.
Input:
8
-1 0
1 0
0 1
0 -4
0 0
1 1
2 2
1 -1
Output:
0 -4

Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.