40分求助
查看原帖
40分求助
151647
sycqwq楼主2020/11/5 13:16

rt

#include<bits/stdc++.h>
#define inf 2147283647
using namespace std;
const int maxn=5e5;
int n;
struct node
{
    int id,x,y;
}a[maxn],t1[maxn],t2[maxn],t3[maxn],t4[maxn];
int cmp(node s1,node s2)
{
    return s1.x<s2.x;
}
int cmp1(node s1,node s2)
{
    return s1.y>s2.y;
}
int cmp2(node s1,node s2)
{
    return s1.y<s2.y;
}
int cmp3(node s1,node s2)
{
    return s1.x>s2.x;
}
int s=inf;
int bk[maxn];
void js(int x,int y,int z,int k)
{
    // cout<<x<<' '<<y<<' '<<z<<' '<<k<<endl;
    memset(bk,0,sizeof(bk));
    for(int i=1;i<=k;i++)
    {
        bk[t3[i].id]=1; 
    }
    for(int i=1;i<=z;i++)
    {
        if(bk[t4[i].id])
        {
            ++z;
        }
        else
        {
            bk[t4[i].id]=1;
        }
        
    }
    for(int i=1;i<=x;i++)
    {
        if(bk[t3[i].id])
            ++x;
        else
        {
            bk[t3[i].id]=1;
        }
    }
    for(int i=1;i<=y;i++)
    {
        if(bk[t2[i].id])
        {
            ++y;
        }
        else
        {
            bk[t2[i].id]=1;
        }
    }
    if(k==0)
    for(int i=1;i<=n;i++)
    {

        if(bk[t1[i].id]==1)
        {
            ++k;
        } 
        else
        {
            break;
        }
        
    }
    else
    {
            
    for(int i=k+1;i<=n;i++)
    {

        if(bk[t1[i].id]==1)
        {
            ++k;
        } 
        else
        {
            break;
        }
        
    }
    }
    
    if(z==0)
    for(int i=1;i<=n;i++)
    {
        if(bk[t4[i].id])
        {
            ++z;
        }
        else
        { 
            break;
        }
        
    }
    else
    {
        
    for(int i=z+1;i<=n;i++)
    {
        if(bk[t4[i].id])
        {
            ++z;
        }
        else
        { 
            break;
        }
        
    }
    }
    
    if(x==0)
    for(int i=1;i<=n;i++)
    {
        if(bk[t3[i].id])
            ++x;
        else
        {
            break;
        }
    }
    else
    {
        
    for(int i=x+1;i<=n;i++)
    {
        if(bk[t3[i].id])
            ++x;
        else
        {
            break;
        }
    }
    }
    
    if(y==0)
    for(int i=1;i<=n;i++)
    {
        if(bk[t2[i].id])
        {
            ++y;
        }
        else
        {
            break;
        }
    }
    else
    {
        
    for(int i=y+1;i<=n;i++)
    {
        if(bk[t2[i].id])
        {
            ++y;
        }
        else
        {
            break;
        }
    }
    }
    
    /*
    x:小y
    y:大y
    z:大x
    */
    // cout<<x<<' '<<y<<' '<<z<<' '<<k<<endl;
    // cout<<t2[y+1].y<<' '<<t3[x+1].y<<' '<<t4[z].x<<' '<<t1[k+1].x<<endl;
    // cout<<(t2[y+1].y-t3[x+1].y+1)*(t4[z+1].x-t1[k+1].x+1)<<endl;
    s=min(s,(t2[y+1].y-t3[x+1].y)*(t4[z+1].x-t1[k+1].x));
    if(s==10)
        getchar();
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
        a[i].id=i;
        t1[i]=a[i];
        t2[i]=a[i];
        t3[i]=a[i];
        t4[i]=a[i];
    }
    sort(t1+1,t1+1+n,cmp);
    sort(t2+1,t2+1+n,cmp1);
    sort(t3+1,t3+1+n,cmp2);
    sort(t4+1,t4+1+n,cmp3);
    for(int i=0;i<=3;i++)
        for(int j=0;i+j<=3;j++)
            for(int k=0;i+j+k<=3;k++)
            {
                for(int l=0;i+j+k+l<=3;l++)
                {
                    js(i,j,k,l);
                }
            }
    cout<<s;
    return 0;
}
2020/11/5 13:16
加载中...