[HAOI2007]覆盖问题

Time Limit:10000MS  Memory Limit:165536K
Total Submit:17 Accepted:8
Case Time Limit:1000MS

Description

某人在山上种了N棵小树苗。冬天来了，温度急速下降，小树苗脆弱得不堪一击，于是树主人想用一些塑料薄膜把这些小树遮盖起来，经过一番长久的思考，他决定 用3个L*L的正方形塑料薄膜将小树遮起来。我们不妨将山建立一个平面直角坐标系，设第i棵小树的坐标为（Xi,Yi），3个L*L的正方形的边要求平行 与坐标轴，一个点如果在正方形的边界上，也算作被覆盖。当然，我们希望塑料薄膜面积越小越好，即求L最小值。

Input

第一行有一个正整数N，表示有多少棵树。
接下来有N行，第i+1行有2个整数Xi,Yi，表示第i棵树的坐标，保证不会有2个树的坐标相同。

Output

一行，输出最小的L值。

Sample Input

4
0 1
0 -1
1 0
-1 0

Sample Output

1
数据范围
100%的数据，-1,000,000,000<=Xi,Yi<=1,000,000,000
30%的数据，N<=100
50%的数据，N<=2000
100%的数据，N<=20000

Source

这题直接将我虐成SB。。。。
首先这是SGU的原题，309.。
但这并不能帮助我们做题囧。。。。
以前写过一个贪心。。果断WA。。
首先二分。。
当时想的是肯定要选一个角上的正方形（这个可以证）
然后自然想肯定要选2个角上的正方形（这个不会证，实际上是错的我擦），
然后检查剩下的时候能包裹在一个正方形里面。。。。
WA。。。WA。。。WA。。。
后来发现了反例我擦。。。
然后想到第一个是对的，那我第一个包含的所有点给去掉，再找一次也是对的。。。
然后就AC了。。。
不过SGU上TLE了。。。