#USACO514. Cave Cows 3

Cave Cows 3

[USACO04OPEN] Cave Cows 3

题目描述

约翰的 N N ( 1N50000 1 \leq N \leq 50000 )只牛在一个黑魃魃的洞里探险,他们只能通过叫声交流。

两只牛之间的曼哈顿距离决定了声音传播的时间。即牛1与牛2交流,需要的时间为 x1x2+y1y2 |x_1-x_2|+|y_1-y_2| 。其中 106x1,x2,y1,y2106 -10^6 \leq x_1,x_2,y_1,y_2 \leq 10^6

那任意一对牛之间交流时间的最大值为多少?

输入格式

第1行输入 N N ,接下来每行输入一只牛的坐标。

输出格式

交流时间最大值(即最大曼哈顿距离)。

样例 #1

样例输入 #1

5
1 1
3 5
2 7
8 1
4 4

样例输出 #1

12

提示

样例解释:

(2,7) (2,7) (8,1) (8,1) 两点间的距离最大,为12。