[文章目录]
Description
给定平面上N个点。现你可以删去至多3个点，接着你需要用一个矩形包含所有的点，点可以在矩形的边上，矩形的边须与坐标轴平行。最小化矩形的面积并输出这个值。5 ≤ N ≤ 50000, 1 ≤ X_i, Y_i ≤ 40000
面积=(xmax-xmin)*(ymax-ymin)
那么每次删的点必须对一个参数答案有贡献，所以每层只有4个，直接搜索就好了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,x[51000],y[51000];
long long ans=0x3f3f3f3f3f3f3f3fll;
bool v[51000];
void solve(int left)
{
int xmx,xmi,ymx,ymi; xmi=ymi=inf; xmx=ymx=0; int a,b,c,d;
for(int i=1;i<=n;++i) if(!v[i])
{
if(x[i]>xmx) xmx=x[i],a=i;
if(x[i]<xmi) xmi=x[i],b=i;
if(y[i]>ymx) ymx=y[i],c=i;
if(y[i]<ymi) ymi=y[i],d=i;
}
ans=min(ans,1ll*(xmx-xmi)*(ymx-ymi)); if(left==0) return ;
v[a]=1; solve(left-1); v[a]=0;
v[b]=1; solve(left-1); v[b]=0;
v[c]=1; solve(left-1); v[c]=0;
v[d]=1; solve(left-1); v[d]=0;
}
int main()
{
scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d%d",x+i,y+i);
solve(3); printf("%lld",ans);
return 0;
}