题意：给你n个矩形，然后矩形有可能重叠，要你求周长
思路：首先碰到这种矩形在数轴上那么第一反应应该想到的是扫描线，
做周长我们有两种方法
第一种，我们可以分开两部分求，第一遍求x轴上的贡献，第二遍求y轴上的贡献
首先第一条边我们可以直接加出贡献，第二条边我们和第一条有覆盖部分，那么我们要怎么加呢，我们会发现要加的也就是 （ 加入这条边后的线段树上最大长度-没加之前的最大长度）
然后我们再加进来，会看到加入出边的时候因为是-1了，所以加入后的长度会比没加之前的值小，但是贡献依然是他们的差值，那么我们就只要求绝对值即可
y轴上是一样的道理
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<cstdlib> #include<algorithm> #define mem(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f #define N 10005 #define ll long long using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct Seg { int l,r,h; int f; Seg() {} Seg(int a,int b,int c,int d):l(a),r(b),h(c),f(d) {} bool operator < (const Seg &cmp) const { return h<cmp.h; } } e[N],e2[N]; struct node { int cnt; int len; } t[N<<2]; int X[N]; int Y[N]; void pushdown(int l,int r,int rt,int X[]) { if(t[rt].cnt)//当前的边被标记，就把当前的长度加上 t[rt].len=X[r+1]-X[l]; else if(l==r)//当为一个点的时候长度为0 t[rt].len=0; else//其他情况把左右两个区间的值加上 t[rt].len=t[rt<<1].len+t[rt<<1|1].len; } void update(int L,int R,int l,int r,int rt,int val,int X[]) { if(L<=l&&r<=R) { t[rt].cnt+=val;//加上标记的值 pushdown(l,r,rt,X);//像下更新节点 return; } int m=(l+r)>>1; if(L<=m) update(L,R,lson,val,X); if(R>m) update(L,R,rson,val,X); pushdown(l,r,rt,X); } int main() { int n; int a,b,c,d; while(scanf("%d",&n)!=EOF) { mem(t,0); int num=0; for(int i=0; i<n; i++) { scanf("%d%d%d%d",&a,&b,&c,&d); X[num]=a;Y[num]=b; e[num]=Seg(a,c,b,1);//矩形下面用1来标记吗 e2[num++]=Seg(b,d,a,1); X[num]=c;Y[num]=d; e[num]=Seg(a,c,d,-1);//上面用-1来标记 e2[num++]=Seg(b,d,c,-1); } sort(Y,Y+num); sort(X,X+num);//用于离散化 sort(e,e+num);//把矩形的边的纵坐标从小到大排序 sort(e2,e2+num); int m=unique(X,X+num)-X; int m2=unique(Y,Y+num)-Y; int ans=0; int last=0; for(int i=0; i<num; i++) { int l=lower_bound(X,X+m,e[i].l)-X;//找出离散化以后的值 int r=lower_bound(X,X+m,e[i].r)-X-1; update(l,r,0,m,1,e[i].f,X); ans+=abs(last-t[1].len); last=t[1].len; } last=0; memset(t,0,sizeof(t)); for(int i=0; i<num; i++) { int l=lower_bound(Y,Y+m2,e2[i].l)-Y;//找出离散化以后的值 int r=lower_bound(Y,Y+m2,e2[i].r)-Y-1; update(l,r,0,m2,1,e2[i].f,Y); ans+=abs(last-t[1].len); last=t[1].len; } printf("%d ",ans); } return 0; }
第二种我暂时不会，先空着，只要求一遍扫描线