Compania de telefonie mobilă BytePhone are instalate în oraşul New Flatbyte n antene GSM, numerotate de la 1 la n. În timpul convorbirilor fiecare abonat al companiei este conectat la cea mai apropiată antenă de el. Pentru a îmbunătăţi calitatea serviciilor, conducerea companiei doreşte să realizeze un studiu, care va determina zona de oraş deservită de o singură antenă având arie maximă.
Oraşul New Flatbyte este amplasat pe un teren dreptunghiular. Laturile terenului sunt respectiv paralele cu axele de coordonate. Coordonatele colţului stâng-jos şi ale colţului drept-sus ale terenului pe care este amplasat oraşul sunt numere întregi.
Antenele punctiforme sunt descrise prin coordonatele lor carteziene – perechi de numere întregi (xi, yi) (1≤i≤n). Distanţa de la un punct arbitrar de coordonate (x,y) până la antena i este distanţa euclidiană (sqrt(x-xi)2+(y-yi)2) Pentru o calitate mai bună a semnalului nu există două antene situate pe aceeaşi linie orizontală sau pe aceeaşi linie verticală şi nu există trei antene amplasate pe aceeaşi dreaptă.
S-a convenit că ariile calculate se rotunjesc până la cel mai apropiat număr întreg, mai mare sau egal cu valoarea determinată. De exemplu, dacă a fost calculată aria de 45.23 , ea se va considera fiind egală cu 46.
Cerinţă
Scrieţi un program, care va determina indicele i al antenei, care deserveşte o zonă de oraş de arie maximă. Dacă există mai multe antene, care deservesc zone cu arie maximă, se va indica antena cu indicele minim.
Date de intrare
Fişierul text gsm.in va conţine pe prima linie un număr natural n – numărul de antene în oraş. Următoarele n linii conţin câte o pereche de numere întregi x y separate prin spaţiu – coordonatele poziţiilor antenelor. În linia i+1 a fişierului se află coordonatele antenei i. Linia n+2 a fişierului conţine patru numere întregi, separate prin spaţiu – coordonatele vârfurilor diagonale ale dreptunghiului, care delimitează oraşul, în ordinea: x1 y1 x2 y2.
Date de ieşire
Fişierul text gsm.out va conţine o singură linie pe care va fi scris un număr întreg reprezentând indicele antenei, care deserveşte o zonă de oraş de suprafaţă maximă.
Restricţii
3 ≤ n ≤ 200
0 ≤ x, y ≤1000 (atât pentru coordonatele antenelor, cât şi pentru ale terenului)
Exemple
gsm.in
gsm.out
Explicatii
3
1 1
10 2
4 8
0 0 12 12
3
Dreptunghiul este divizat în poligoane convexe, fiecare dintre ele descrie zona deservită de o antenă.
Ariile reale ale poligoanelor sunt 2.4114285714E+01
4.3950000000E+01
7.5935714286E+01
Cea mai mare arie (75.94≈76) este a zoneicare corespunde antenei 3.
