Motherboard
Турнир за Купата на Декана, 2016
Time Limit: 0.1s, Memory Limit: 64MiB
Правецът, който си купи Ели, не й е достатъчен за изчисленията, които прави тя. Всъщност, никой наличен хардуер не е. Затова момичето е решило само да си сглоби компютър. Колко пък сложно може да е това!?

Най-важното нещо в един компютър е неговият процесор, или процесорИ, както е в случая с машината на Ели. Също е важно как те комуникират помежду си. За целта, на дънната платка има главна шина, която представлява хоризонтален сноп от златни нишки, по които тече информация. Всеки от процесорите е разположен над или под тази шина и е свързан с нея чрез вертикална нишка. За да си комуникират два процесора A и B, трябва сигналът от A да стигне до главната шина (вертикално), след което по нея да стигне до вертикалната нишка на процесора B (хоризонтално) и накрая да отиде до B по нея (вертикално). За простота считаме, че скоростта на комуникация се определя от изминатото разстояние на сигнала – тоест сумата на разстоянието между A и B по хоризонтала и разстоянията от A и B до главната шина по вертикала.

По ред причини местата на процесорите са вече определени по дънната платка и не могат да бъдат променяни. За сметка на това, позицията (Y-координатата) на главната шина не е. Сега Ели се чуди къде точно да бъде тя, така че най-бавната комуникация между процесори да е възможно най-бърза.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N – броя процесори, които има съответната дънна платка. Следват N реда, всеки съдържащ по две цели числа Xi и Yi – координатите на процесорите. Считаме, че няма два процесора с една и съща X-координата (това гарантира, че техните нишки няма да се припокриват или докосват).
Изход
На стандартния изход изведете едно цяло число – най-голямото разстояние между два процесора, ако главната шина бъде поставена оптимално.
Ограничения
  • 1 ≤ N ≤ 100
  • -1,000,000,000 ≤ Xi, Yi ≤ 1,000,000,000
Примерен Вход Примерен Изход
5 1 1 -2 5 4 0 3 3 -3 -2 11
Ако главната шина е с Y = 0, то най-голямото разстояние би било 13 (между точките (-2, 5) и (3, 3)). Ако, обаче, шината е с Y = 1, най-голямото разстояние би било по-малко – само 11 – този път между (-3, -2) и (4, 0).
Мрън!