BZOJ 4581: [Usaco2016 Open]Field Reduction

时间：2021-10-27 03:31:38

Description

有 \(n\) 个点,删掉三个点后,求最小能围住的面积.

Sol

搜索.

找出 左边/右边/上边/下边 的几个点枚举就可以了.

我找了 12 个点,统计一下坐标的个数,然后找到最大最小坐标.

PS:md.Cena 好像对 STL 不太友好啊,用 map 居然T了???exm???

昨天用 map 离散化就T的飞起.md..mama我再也不用 map 离散化了...以后用lower_bound()好了...

一开始写了个DFS来枚举...发现不是很好...又删掉变成三维循环枚举...代码奇丑无比...

Code

/**************************************************************

    Problem: 4581

    User: BeiYu

    Language: C++

    Result: Accepted

    Time:440 ms

    Memory:5168 kb

****************************************************************/

#include <cstdio>

#include <map>

#include <utility>

#include <algorithm>

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 50050;

const int M = 15;

int C = 12;

struct P{ int x,y,id; };

bool operator < (const P &a,const P &b){ return a.x==b.x?a.y<b.y:a.x<b.x; }

bool operator == (const P &a,const P &b){ return (a.x==b.x) && (a.y==b.y); }

int n;LL ans;

int b[N],xx[N],yy[N],cx[N],cy[N];

P a[N],p[N];

P mxx[M],mxy[M],mix[M],miy[M];

P del[M];

map< int,int > mpx,mpy;

inline int in(int x=0){ scanf("%d",&x);return x; }

/*

LL calc(){

//  cout<<"--------------"<<endl;

//  for(int i=1;i<=3;i++) cout<<del[i].x<<" "<<del[i].y<<endl;

    int minx=1,maxx=n,miny=1,maxy=n;

    for(int i=3;i>=1;i--){

        if(del[i].x == xx[minx]) minx++;

        if(del[i].x == xx[maxx]) maxx--;

        if(del[i].y == yy[miny]) miny++;

        if(del[i].y == yy[maxy]) maxy--;

    }

    for(int i=3;i>=1;i--){

        if(del[i].x == xx[minx]) minx++;

        if(del[i].x == xx[maxx]) maxx--;

        if(del[i].y == yy[miny]) miny++;

        if(del[i].y == yy[maxy]) maxy--;

    }

    for(int i=3;i>=1;i--){

        if(del[i].x == xx[minx]) minx++;

        if(del[i].x == xx[maxx]) maxx--;

        if(del[i].y == yy[miny]) miny++;

        if(del[i].y == yy[maxy]) maxy--;

    }

//  cout<<xx[maxx]<<" "<<xx[minx]<<" "<<yy[maxy]<<" "<<yy[miny]<<endl;

//  cout<<1LL*(xx[maxx]-xx[minx])*(yy[maxy]-yy[miny])<<endl;

    return 1LL*(xx[maxx]-xx[minx])*(yy[maxy]-yy[miny]);

}

void DFS(int w,int d){

    if(w==4 || d==0){ if(!d) ans=min(ans,calc());return; }

    int c=0;

    DFS(w+1,d);

    int tmp[M];

    switch(w){

        case 0:

            for(int i=1;i<=C;i++){

                if(c>d) break;

                if(!b[mix[i].id]) tmp[++c]=mix[i].id,del[d-c+1]=mix[i],b[mix[i].id]=1,DFS(w+1,d-c);

            }break;

        case 1:

            for(int i=1;i<=C;i++){

                if(c>d) break;

                if(!b[mxx[i].id]) tmp[++c]=mxx[i].id,del[d-c+1]=mxx[i],b[mxx[i].id]=1,DFS(w+1,d-c);

            }break;

        case 2:

            for(int i=1;i<=C;i++){

                if(c>d) break;

                if(!b[miy[i].id]) tmp[++c]=miy[i].id,del[d-c+1]=miy[i],b[miy[i].id]=1,DFS(w+1,d-c);

            }break;

        case 3:

            for(int i=1;i<=C;i++){

                if(c>d) break;

                if(!b[mxy[i].id]) tmp[++c]=mxy[i].id,del[d-c+1]=mxy[i],b[mxy[i].id]=1,DFS(w+1,d-c);

            }break;

    }

    for(int i=1;i<=c;i++) b[tmp[i]]=0;

    return;

}*/

int main(){ n=in();C=min(C,n),ans=1e18;

    for(int i=1;i<=n;i++) a[i].x=in(),a[i].y=in(),a[i].id=i;

    for(int i=1;i<=n;i++) xx[i]=a[i].x,yy[i]=a[i].y;

    sort(xx+1,xx+n+1),sort(yy+1,yy+n+1);

    cx[0]=unique(xx+1,xx+n+1)-(xx+1),cy[0]=unique(yy+1,yy+n+1)-(yy+1);

    for(int i=1;i<=cx[0];i++) mpx[xx[i]]=i;

    for(int i=1;i<=cy[0];i++) mpy[yy[i]]=i;

    for(int i=1;i<=n;i++) cx[mpx[a[i].x]]++,cy[mpy[a[i].y]]++;

    int cnt=0;

    sort(a+1,a+n+1);

    for(int i=1;i<=C;i++) p[++cnt]=a[i];

    for(int i=1;i<=n;i++) a[i].x=-a[i].x;

    sort(a+1,a+n+1);

    for(int i=1;i<=C;i++) p[++cnt]=a[i],p[cnt].x=-p[cnt].x;

    for(int i=1;i<=n;i++) a[i].x=-a[i].x,swap(a[i].x,a[i].y);

    sort(a+1,a+n+1);

    for(int i=1;i<=C;i++) p[++cnt]=a[i],swap(p[cnt].x,p[cnt].y);

    for(int i=1;i<=n;i++) a[i].x=-a[i].x;

    sort(a+1,a+n+1);

    for(int i=1;i<=C;i++) p[++cnt]=a[i],p[cnt].x=-p[cnt].x,swap(p[cnt].x,p[cnt].y);

    sort(p+1,p+cnt+1);

//  for(int i=1;i<=cnt;i++) cout<<p[i].x<<" "<<p[i].y<<endl;

    cnt=unique(p+1,p+cnt+1)-(p+1);

//  for(int i=1;i<=cnt;i++) cout<<p[i].x<<" "<<p[i].y<<endl;

    for(int i=1;i<=cnt;i++) for(int j=i+1;j<=cnt;j++) for(int k=j+1;k<=cnt;k++){

        cx[mpx[p[i].x]]--,cx[mpx[p[j].x]]--,cx[mpx[p[k].x]]--;

        cy[mpy[p[i].y]]--,cy[mpy[p[j].y]]--,cy[mpy[p[k].y]]--;

        int minx=1,maxx=cx[0],miny=1,maxy=cy[0];

        while(!cx[minx]) minx++;

        while(!cx[maxx]) maxx--;

        while(!cy[miny]) miny++;

        while(!cy[maxy]) maxy--;

        ans=min(ans,1LL*(xx[maxx]-xx[minx])*(yy[maxy]-yy[miny]));

        cx[mpx[p[i].x]]++,cx[mpx[p[j].x]]++,cx[mpx[p[k].x]]++;

        cy[mpy[p[i].y]]++,cy[mpy[p[j].y]]++,cy[mpy[p[k].y]]++;

    }

//  for(int i=1;i<=n;i++) cout<<xx[i]<<" ";cout<<endl;

//  for(int i=1;i<=n;i++) cout<<yy[i]<<" ";cout<<endl;

//  sort(a+1,a+n+1);

//  for(int i=1;i<=C;i++) mix[i]=a[i];

//

//  for(int i=1;i<=n;i++) a[i].x=-a[i].x;

//  sort(a+1,a+n+1);

//  for(int i=1;i<=C;i++) mxx[i]=a[i],mxx[i].x=-mxx[i].x;

//

//  for(int i=1;i<=n;i++) a[i].x=-a[i].x,swap(a[i].x,a[i].y);

//  sort(a+1,a+n+1);

//  for(int i=1;i<=C;i++) miy[i]=a[i],swap(miy[i].x,miy[i].y);

//

//  for(int i=1;i<=n;i++) a[i].x=-a[i].x;

//  sort(a+1,a+n+1);

//  for(int i=1;i<=C;i++) mxy[i]=a[i],mxy[i].x=-mxy[i].x,swap(mxy[i].x,mxy[i].y);

//  cout<<"--------------"<<endl;

//  for(int i=1;i<=C;i++) cout<<mix[i].x<<" "<<mix[i].y<<endl;

//  cout<<"--------------"<<endl;

//  for(int i=1;i<=C;i++) cout<<mxx[i].x<<" "<<mxx[i].y<<endl;

//  cout<<"--------------"<<endl;

//  for(int i=1;i<=C;i++) cout<<miy[i].x<<" "<<miy[i].y<<endl;

//  cout<<"--------------"<<endl;

//  for(int i=1;i<=C;i++) cout<<mxy[i].x<<" "<<mxy[i].y<<endl;

//  cout<<"--------------"<<endl;

//  DFS(0,3);

    cout<<ans<<endl;

    return 0;

}

　　

相关文章