codevs 2149 矩形周长(暴力扫描线)

时间:2021-01-24 21:38:35
/*
暴力应该很好理解 不多说了
至于线段树维护的嘛 还没看懂
哪天突然想明白了在写吧
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 5010
#define bas 10000
using namespace std;
int n,m,f[maxn*],ans;
struct node{
int l,r,h,t;
}A[maxn*],B[maxn*];
int cmp(const node &a,const node &b){
if(a.h==b.h)return a.t<b.t;
return a.h<b.h;
}
int main()
{
freopen("picture.in","r",stdin);
freopen("picture.out","w",stdout);
scanf("%d",&n);
int x1,x2,y1,y2;
for(int i=;i<=n;i++){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1+=bas;x2+=bas;y1+=bas;y2+=bas;
A[++m].l=x1;A[m].r=x2;A[m].h=y1;A[m].t=;
B[m].l=y1;B[m].r=y2;B[m].h=x1;B[m].t=;
A[++m].l=x1;A[m].r=x2;A[m].h=y2;A[m].t=;
B[m].l=y1;B[m].r=y2;B[m].h=x2;B[m].t=;
}
sort(A+,A++m,cmp);sort(B+,B++m,cmp);
for(int i=;i<=m;i++){
int l=A[i].l,r=A[i].r;
for(int j=l;j<r;j++){
if(A[i].t==){if(f[j]==)ans++;f[j]++;}
else{f[j]--;if(f[j]==)ans++;}
}
}
memset(f,,sizeof(f));
for(int i=;i<=m;i++){
int l=B[i].l,r=B[i].r;
for(int j=l;j<r;j++){
if(B[i].t==){if(f[j]==)ans++;f[j]++;}
else{f[j]--;if(f[j]==)ans++;}
}
}
printf("%d\n",ans);
}