526互联

Field Reduction USACO - 641

发布时间 2023-06-09 09:40:14作者: Cruzz

题目链接：http://www.usaco.org/index.php?page=viewproblem2&cpid=641&lang=en

题意：有n (3<n<50000) 头牛 你需要给这n头牛建造围栏。坐标范围1-40,000。围栏的面积越小越好。你需要删除1头牛来减小围栏面积

思路：1. 因为只能删除1头牛来减少围栏面积，所以只能删除最靠边缘的牛，否则不会影响围栏的面积

　　　2. 所以可删除的牛范围就在x最大，y最大，x最小，y最小的4条边上

　　　3. 其次，如果那一条边上有2头牛，删除1头也没有用，所以直接考虑别的边

　　　4. 4条边全部枚举完后 算出最小面积

AC代码：

#include<bits/stdc++.h>
using namespace std;
long long n,maxx,minx,maxy,miny,cnt1,cnt2,cnt3,cnt4,tmp1,tmp2,tmp3,tmp4,c1;
long long ans=2e10;
int main(void) {
    freopen("reduce.in","r",stdin);
    freopen("reduce.out","w",stdout);
    struct cow {
        int x;
        int y;
    };
    cow a[55555];
    cin>>n;
    for(int i=0; i<n; i++) {
        cin>>a[i].x>>a[i].y;
    }
    //确定4条边
    for(int i=0; i<n; i++) {
        if(a[i].x>a[maxx].x) {
            maxx=i;
        }
        if(a[i].x<a[minx].x) {
            minx=i;
        }
        if(a[i].y>a[maxy].y) {
            maxy=i;
        }
        if(a[i].y<a[miny].y) {
            miny=i;
        }
    }
    ans=(a[maxx].x-a[minx].x)*(a[maxy].y-a[miny].y);
    //测试cout<<maxx<<endl<<minx<<endl<<maxy<<endl<<miny;
    //确定边上牛数量 必须=1 否则删了也没用
    for(int i=0; i<n; i++) {
        //左边
        if(a[minx].x==a[i].x) {
            cnt1++;
        }
        //右边
        if(a[maxx].x==a[i].x) {
            cnt2++;
        }
        //上边
        if(a[maxy].y==a[i].y) {
            cnt3++;
        }
        //下边
        if(a[miny].y==a[i].y) {
            cnt4++;
        }
    }
    //判断得出距离最近的牛的距离
    if(cnt1==1) {
        int max_x=0,max_y=0,min_x=100000,min_y=100000;
        for(int i=0; i<n; i++) {
            if(a[i].x>a[minx].x) {
                max_x=max(max_x,a[i].x);
                max_y=max(max_y,a[i].y);
                min_x=min(min_x,a[i].x);
                min_y=min(min_y,a[i].y);
            }
        }
        tmp1=(max_y-min_y)*(max_x-min_x);
        ans=min(ans,tmp1);
    }
    if(cnt2==1) {
        int max_x=0,max_y=0,min_x=100000,min_y=100000;
        for(int i=0; i<n; i++) {
            if(a[i].x<a[maxx].x) {
                max_x=max(max_x,a[i].x);
                max_y=max(max_y,a[i].y);
                min_x=min(min_x,a[i].x);
                min_y=min(min_y,a[i].y);
            }
        }
        tmp2=(max_y-min_y)*(max_x-min_x);
        ans=min(ans,tmp2);
    }
    if(cnt3==1) {
        int max_x=0,max_y=0,min_x=100000,min_y=100000;
        for(int i=0; i<n; i++) {
            if(a[i].y<a[maxy].y) {
                max_x=max(max_x,a[i].x);
                max_y=max(max_y,a[i].y);
                min_x=min(min_x,a[i].x);
                min_y=min(min_y,a[i].y);
            }
        }
        tmp3=(max_y-min_y)*(max_x-min_x);
        ans=min(ans,tmp3);
    }
    if(cnt4==1) {
        int max_x=0,max_y=0,min_x=100000,min_y=100000;
        for(int i=0; i<n; i++) {
            if(a[i].y>a[miny].y) {
                max_x=max(max_x,a[i].x);
                max_y=max(max_y,a[i].y);
                min_x=min(min_x,a[i].x);
                min_y=min(min_y,a[i].y);
            }
        }
        tmp4=(max_y-min_y)*(max_x-min_x);
        ans=min(ans,tmp4);
    }
    //求出最小面积
    cout<<ans<<endl;
    return 0;
}

 

求围栏最小面积