Robottávolság

Egy nagy áruházban egy robot megadott helyszínek között tud mozogni. A helyszínek a koordinátáikkal vannak megadva. A robot csak a koordináta-rendszer tengelyeivel párhuzamosan tud mozogni. Ez azt jelenti, hogy ha a robot el akar jutni a p = (x₁, y₁) helyszínről a q = (x₂, y₂) helyszínre, akkor először az (x₂, y₁) helyszínre, majd onnan a q = (x₂, y₂) helyszínre kell mennie. Így a robot által megtett távolság |x₂ − x₁| + |y₂ − y₁|. Ezt az értéket a p és q helyszínek robottávolságának nevezzük.

Egy olyan programot kell írnod, amely helyszínek egy adott halmaza esetén kiszámítja a halmazbeli helyszínek közötti legnagyobb robottávolságot.

A bemenet specifikációja

A bemenet tesztesetek blokkjait tartalmazza. Minden teszteset első sora egyetlen n egész számot tartalmaz (2 ≤ n ≤ 100 000), amely a helyszínek száma. A következő n sor mindegyike két egész számot tartalmaz, x-et és y-t, az egyes helyszínek koordinátáit (−100 000 000 ≤ x, y ≤ 100 000 000).

A bemenet egy olyan blokkal ér véget, amelyben n = 0.

A kimenet specifikációja

A bemenet minden egyes tesztesetére egy-egy egész számot kell kiírnod, mindegyiket külön sorba: a bemeneten megadott helyszínek közötti legnagyobb robottávolságot.

Példa bemenet

1. 8
2. 2 3
3. 4 1
4. 7 7
5. 6 5
6. 8 10
7. 0 8
8. 4 7
9. 2 5
10. 4
11. 1 5
12. 3 0
13. 4 7
14. 3 3
15. 0

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 13
2. 8

letöltés szöveges állományként