[Usaco2016 Open]Field Reduction

题目大意

农夫约翰的N(5<=N<=50000)头牛被定在了平面内的不同的位置。他想用栅栏(平行于x和y轴)围住所有的牛。他想这个栅栏尽可能小(牛在边界上也被视作围住)。 他因为牛奶产量低而感到经费紧张，所以他想卖掉三头牛再围起剩下的牛。请算出栅栏围出的最小面积。(面积有可能为0，例如，最后剩下的牛排成一排或一列。） Input Format 第一行输入正整数n 剩下2-n+1行，输入每头牛的坐标位置(x,y) ( 1<= x,y<=40000的整数） Output Format 最小面积 Sample Input 6 1 1 7 8 10 9 8 12 4 100 50 7 Sample Output 12

分析

这道题的面积是一个矩形，所以这道题就比较简单了。我先将各个方向的最前面四个点存入一个数组（不能有相同的点）。因为有可能这四个点在同一行或列中，但我们只能删去三个点，所以这个方向就是不可行的。另外有可能会将三个在同一行或列中的点删去，所以我们要取第四个点来，方便计算面积。 我们只需要在取出的点中枚举3个，然后计算面积取min就好了。 INF不要开太小，这个最大的面积是40000的平方，我之前只开0x3fffffff，所以调了很久才出来

代码

#include<cstdio> #include<cstring> #include<algorithm> #define MAXN 50007 #define INF 40000*40000+10//INF太小 using namespace std; int n,sum,ans=INF; bool vis[MAXN]; struct node { int x,y; int id; }a[MAXN]; struct ant { int x,y; int id; }b[20]; bool cmp1(node p,node q) { return p.x<q.x; } bool cmp2(node p,node q) { return p.y<q.y; } void check(int x,int y,int z) { //printf("%d %d %d\n",x,y,z); int maxx=0,maxy=0,minx=INF,miny=INF; for(int i=1;i<=sum;i++) { if(i==x||i==y||i==z) continue; maxx=max(maxx,b[i].x); minx=min(minx,b[i].x); maxy=max(maxy,b[i].y); miny=min(miny,b[i].y); } ans=min(ans,(maxx-minx)*(maxy-miny)); return; } int main() { freopen("reduce.in","r",stdin); freopen("reduce.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].x,&a[i].y); a[i].id=i; } sort(a+1,a+n+1,cmp1); for(int i=1;i<=4;i++) { if(!vis[a[i].id]) { vis[a[i].id]=1; b[++sum].x=a[i].x; b[sum].y=a[i].y; b[sum].id=a[i].id; } } for(int i=n;i>=n-3;i--) { if(!vis[a[i].id]) { vis[a[i].id]=1; b[++sum].x=a[i].x; b[sum].y=a[i].y; b[sum].id=a[i].id; } } sort(a+1,a+n+1,cmp2); for(int i=1;i<=4;i++) { if(!vis[a[i].id]) { vis[a[i].id]=1; b[++sum].x=a[i].x; b[sum].y=a[i].y; b[sum].id=a[i].id; } } for(int i=n;i>=n-3;i--) { if(!vis[a[i].id]) { vis[a[i].id]=1; b[++sum].x=a[i].x; b[sum].y=a[i].y; b[sum].id=a[i].id; } } for(int i=1;i<=sum;i++) { for(int j=1;j<=sum;j++) { if(i==j) continue; for(int k=1;k<=sum;k++) { if(i==k||j==k) continue; check(i,j,k); } } } printf("%d",ans); }