A1 - Anténa 1

Časový limit: 2s, 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 ]

Úloha

Záhradkársky zväz sa chystá povýšiť svoju oblasť na "smart", teda umiestniť rôzne zariadenia (senzory, osvetlenie a ďalšie) v rámci tejto oblasti a pokryť ich signálom 5G. Majú však problém. Radi by postavili anténu, ktorá by svojim signálom pokryla všetky zariadenia v záhradkárskej oblasti. Takéto výkonné antény sú ale veľmi drahé, preto sa snažia znížiť svoje náklady na minimum. Cena antény priamo závisí od veľkosti uhla, pod ktorým musí vysielať svoj signál pričom platí: čím väčší uhol pokrytia, tým vyššia cena. Majú pripavení plánik všetkých pripojených zariadení a Vašou úlohou bude nájsť zariadenia, pri ktorom je možné umiestniť čo najlacnejšiu anténu tak, aby boli signálom pokryté úplne všetky zariadenia v oblasti. Zariadenie, na ktorom sa anténa nachádza pokladajte automaticky za pokryté signálom.

Vstup

Prvý riadok vstupu obsahuje prirodzené číslo N, počet zariadení v záhradkárskej oblasti. Ďalších N riadkov obsahuje po dve celé čísla X,Y, -10 000 ≤ X,Y ≤ 10 000, súradnice zariadenia. Môžete predpokladať, že žiadne dve zariadenia nemajú rovnaké súradnice.

Výstup

Vypíšte jediný riadok s číslom zariadenia na vstupe. Ak je z viacerých zariadení rovnaký uhol, vypíšte ten, ktorý sa najskôr objavil na vstupe, teda má najnižšie poradové číslo. Zariadenia vstupe sú číslované od 1.

Poznámka

Dva uhly A,B môžeme pokladať za rovnaké, ak platí abs(A-B) < 0.01 v stupňoch.

A1

1 ≤ N ≤ 2 000

A2

1 ≤ N ≤ 15 000

Príklad 1

Vstup:

Výstup:

Vysvetlenie:

Zariadenia formujú vrcholy štvorca. Anténa by na každom zariadení pokrývala ostatné presne pod uhlom 90 stupňov, preto je správny výsledok prvé zariadenie v poradí.

Príklad 2

Vstup:

Výstup:

20 Domáce 1