z-dots
U ravni je dat skup S od N tacaka. Koordinate tacaka su celi brojevi. Za svaku od datih tacaka definisemo funkciju
d(A) = sum(B in S) max {| Ax - Bx |, | Ay - By |}
Naci onu tacku za koji je navedena funkcija minimalna.
InputPodaci se ucitavaju sa standardnog ulaza. U prvom redu se nalazi broj N, 1 <= N <= 100.000, koji predstavlja broj tacaka. U narednih N linija se nalaze po dva cela broja iz segmenta [-10000, 10000] odvojena jednim razmakom, koji predstavljaju koordinate tacaka.
OutputNa standardnom izlazu, u jednoj liniji stampati indeks tacke (u pocetnom nizu) za koja se minimizuje gornja funkcija. Ukoliko postoji vise resenja, stampati najmanje.
Indeksi tacaka su iz segmenta od 0 do N - 1
Ulaz:
Izlaz:
3
0 0
1 1
3 0Izlaz:
1 Objasnjenje: Za test primer imamo da su vrednosti funkcije d sledeci:
d(0) = 0 + 1 + 3 = 4
d(1) = 1 + 0 + 2 = 3
d(3) = 3 + 2 + 0 = 5
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.