Menhetn
Među datim skupom tačaka {(x1, y1), (x2, y2), ..., (xn, yn)} ispisati najmanje menhetn rastojanje među njima.
Menhetn rastojanje između tačaka (a, b) i ([], d) se definiše kao |a - c| + |b - d|.
InputU prvom redu standardnog ulaza učitava se prirodni broj n (2 <= n <= 1000). U narednih n redova se učitavaju tačke -- u i-tom redu se učitava tačka (xi, yi) (-100000 <= xi, yi <= 100000), gde su xi i yi celi brojevi.
OutputU prvi i jedini red ispisati najmanje rastojanje.
Ulaz:
[c]5
1 2
4 2
8 3
9 5
15 11
Izlaz:
Objašnjenje:
Među svim parovima tačaka na najmanjem rastojanju se nalaze prva i druga (|1 - 4| + |2 - 2| = 3), i treća i četvrta tačka (|8 - 9| + |3 - 5| = 3).
[c]5
1 2
4 2
8 3
9 5
15 11
Izlaz:
3Objašnjenje:
Među svim parovima tačaka na najmanjem rastojanju se nalaze prva i druga (|1 - 4| + |2 - 2| = 3), i treća i četvrta tačka (|8 - 9| + |3 - 5| = 3).
Ulaz:
Izlaz:
2
-1 1
-1 1Izlaz:
0Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.