#P2218. [HAOI2007] 覆盖问题

    ID: 1234 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>各省省选河南2007贪心二分答案深度优先搜索DFS

[HAOI2007] 覆盖问题

题目描述

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

输入格式

接下来有 NN 行,第 i+1i+1 行有 22 个整数 Xi,YiX_i,Y_i,表示第 ii 棵树的坐标,保证不会有 22 个树的坐标相同。

输出格式

一行,输出最小的 LL 值。

4
0 1
0 -1
1 0
-1 0

1

提示

对于 100%100\% 的数据,1,000,000,000Xi,Yi1,000,000,000-1,000,000,000 \le X_i,Y_i \le 1,000,000,000。

对于 30%30\% 的数据,N100N \le 100。

对于 50%50\% 的数据,N2000N \le 2000。

对于 100%100\% 的数据,N20000N \le 20000。