[USACO 2013 Mar S]Farm Painting

* Line 1: The number of enclosures, N.

* Lines 2..1+N: Each line describes an enclosure by 4 space-separated
integers x1, y1, x2, and y2, where (x1,y1) is the lower-left
corner of the enclosure and (x2,y2) is the upper-right corner.
All coordinates are in the range 0..1,000,000.

C++14(g++5.4) 解法, 执行用时: 356ms, 内存消耗: 1232K, 提交时间: 2020-05-30 09:11:23

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,L,R,ans;
struct nond{
    int x1,y1,x2,y2;
}v[50010];
int cmp(nond a,nond b){
    return a.x1<b.x1;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        v[i].x1=a;v[i].y1=b;v[i].x2=c;v[i].y2=d;
    }
    sort(v+1,v+1+n,cmp);ans=n;
    for(L=1,R=2;R<=n;R++){
        while(v[L].x2<=v[R].x1)    L++;
        for(int i=L;i<=R;i++)
            if(v[R].x1>v[i].x1&&v[R].y2<v[i].y2&&v[i].y1<v[R].y1&&v[i].x2>v[R].x2){ 
                ans--;break;
            }
    }
    cout<<ans;
}

C++11(clang++ 3.9) 解法, 执行用时: 283ms, 内存消耗: 1260K, 提交时间: 2020-05-31 15:04:59

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,ans;
struct ha{
    int x,y,xx,yy;
    bool operator<(const ha&b)const{
        return x<b.x;
    }
}a[N];
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y>>a[i].xx>>a[i].yy;
    sort(a+1,a+1+n);ans=n;
    for (int i=1,j=2;j<=n;j++)
    {
        while (a[i].xx<=a[j].x) i++;
        for(int k=i;k<j;k++)if(a[k].y<a[j].y&&a[k].xx>a[j].xx&&a[k].yy>a[j].yy){ans--;break;}
    }
    cout<<ans<<endl;
    return 0;
}

详情