suitang

时间限制:20s      空间限制:512MB

题目描述

看过隋唐演义的都知道“宇文成都”是天下第二武功高手,就在隋炀帝杨广被奸臣宇文化及(也就是宇文成都的父亲)所逼死,宫中一片大乱,然“宇文成都”是一代豪杰,不愿通过这种方式来取得皇位,于是只身一人与上万瓦岗起义军决战,以死报国。(可惜啊,这么好的一个人,跟错了主)。 
宇文成都 只身一人击退起义军多位大将,就在这时,徐茂公准备下令让所有士兵冲上去活捉 宇文成都 ,然而 宇文成都 已经发现,他甚至记住了所有士兵的位置(在平面直角坐标系上的坐标,均为整数),他现在可以使用师傅传授的武功,将一个长度为L的正方形(平行于坐标轴,顶点坐标为整数)区域全部化为灰烬,L正比与他所消耗的功力,然而因为刚才运力过多,他现在只能使用3次武功,每一次的攻击正方形边长L都相同,三次使用武功后,他的体力总损耗为 L,每一次选择的正方形区域可以不同,也可以相交。现在他要把所有的n个士兵全部消灭,请问他最少要消耗多少体力(即最小正方形边长)?
(每次使用武功可将正方形内部的士兵全部消灭,边界上也算)


输入格式

第一行一个整数n(n个士兵),接下来n行,每行两个整数(xi,yi),表示每个士兵的坐标。


输出格式

共一行,一个整数,表示最小的体力消耗(L)。


样例输入

10
10 3
4 8
9 1
1 6
5 5
9 6
6 7
7 8
2 1
9 7

样例输出

5

提示

100%的数据:1<=n<=20000;-1000000000<=xi,yi<=1000000000;
此题存在版权,故不再支持提交,保留在此只供大家参考题面! 望见谅!


题目来源

没有写明来源

Menuappsclose