【ZJNU 组队赛四：爆搜DFS】 G：Field Reduction

难度

$3/10$ 想到 $dfs$ 就差不多有解题思路了

题意

在二维平面上，有 $N$ 个不同的点。给出每个点的坐标。 你希望丢掉三个点，然后用一个矩形把所有的点全部框起来。 求出那个矩形的最小面积。

数据范围

$5\le N\le 50000$ $1\le X_i,Y_i\le 40000$

思路

暴力枚举三个点，时间复杂度至少为 $O(N^3)$，不可取。我们考虑丢掉哪些点才是对答案有贡献的。 画一个图可得，如果该点是矩形的内部（该点的上面、下面、左边、右边都有点的话，那么删掉该点对目前的答案是不影响的）

那删除之后对答案影响的点，易得是最小围住矩形的边界线上的点。 一个矩形有上下左右四条边。只要某一边上的点全部删掉，围住矩形的面积就可以减小。 那么我们需要枚举每次删除的是哪条边上的那些点。枚举种类最多为 $4^3=64$ 次。那删完了一些点（或者还没删），我们想知道那个最小围住矩形的面积是多少该怎么算呢？我们可以 $O(N)$ 扫描过去，记录所有还没删掉的点的横坐标的最小值和最大值，以及纵坐标的最小值和最大值。思考后易得： $$S=(横坐标最大值-横坐标最小值)\times (纵坐标最大值-纵坐标最小值)$$最后答案对 $S$ 取 $\min$ 即可。

核心代码

时间复杂度 $O(64\times N)$ Times：156(MS)

/* _ __ __ _ _ | | \ \ / / | | (_) | |__ _ _ \ V /__ _ _ __ | | ___ _ | '_ \| | | | \ // _` | '_ \| | / _ \ | | |_) | |_| | | | (_| | | | | |___| __/ | |_.__/ \__, | \_/\__,_|_| |_\_____/\___|_| __/ | |___/ */ int n; struct pt{ int x; int y; }aa[50050]; vector<int>PX[40050]; /// PX[T] 表示储存横坐标为 T 的所有点的编号 vector<int>PY[40050]; /// PY[T] 表示储存纵坐标为 T 的所有点的编号 bool vis[50050]; /// vis[T] 表示已经删掉了点 T int cal(){ /// 计算最小围住的矩形面积 int Max = 0,May = 0; int Mix = INF,Miy = INF; for(int i = 1;i <= n;i ++){ if(vis[i])continue; Max = max(Max,aa[i].x); May = max(May,aa[i].y); Mix = min(Mix,aa[i].x); Miy = min(Miy,aa[i].y); } return (Max - Mix) * (May - Miy); } int dfs(int c,int shu){ /// c表示第几次删除层数（貌似不必要的），shu表示还能删几个点 if(c == 4)return cal(); if(shu == 0)return cal(); int tmp = 0; int MaX = 0; int MaY = 0; int MiX = INF; int MiY = INF; for(int i = 1;i<=n;++i){ /// 算出了最小围住矩形的面积 if(vis[i])continue; /// 也算出了矩形的边界的横纵坐标 MaX = max(MaX,aa[i].x); MaY = max(MaY,aa[i].y); MiX = min(MiX,aa[i].x); MiY = min(MiY,aa[i].y); } tmp = (MaX - MiX) * (MaY - MiY); /// 删掉哪条边？四种情况都一一枚举 /// right if(PX[MaX].size() <= shu){ for(int i = 0;i<PX[MaX].size();++i) vis[PX[MaX][i]] = 1; tmp = min(tmp,dfs(c+1,shu - PX[MaX].size())); for(int i = 0;i<PX[MaX].size();++i) vis[PX[MaX][i]] = 0; } /// left if(PX[MiX].size() <= shu){ for(int i = 0;i<PX[MiX].size();++i) vis[PX[MiX][i]] = 1; tmp = min(tmp,dfs(c+1,shu - PX[MiX].size())); for(int i = 0;i<PX[MiX].size();++i) vis[PX[MiX][i]] = 0; } /// up if(PY[MaY].size() <= shu){ for(int i = 0;i<PY[MaY].size();++i) vis[PY[MaY][i]] = 1; tmp = min(tmp,dfs(c+1,shu - PY[MaY].size())); for(int i = 0;i<PY[MaY].size();++i) vis[PY[MaY][i]] = 0; } /// down if(PY[MiY].size() <= shu){ for(int i = 0;i<PY[MiY].size();++i) vis[PY[MiY][i]] = 1; tmp = min(tmp,dfs(c+1,shu - PY[MiY].size())); for(int i = 0;i<PY[MiY].size();++i) vis[PY[MiY][i]] = 0; } return tmp; } int main() { scanf("%d",&n); for(int i = 1;i <= n;i ++){ scanf("%d%d",&aa[i].x,&aa[i].y); PX[aa[i].x].push_back(i); PY[aa[i].y].push_back(i); } printf("%d",dfs(1,3)); return 0; }