hdu-1255（线段树求面积并）模板
题目链接：传送门
思路：
（1）建立线段的信息，每个线段存储l到r的线段的x位置和y的起始点与终点。
建立线段树的节点信息，每个节点代表一个区间的信息，x表示区间的横坐标的位置，l，r表示纵坐标的范围，flag表示是否标记过，cover表示线段的覆盖次数。
（2）先将y的位置按照从小到大排序，再将边按照x的先后位置排序，然后建树，这样可以依次求出那部分被覆盖了。
（3）建树：如果不是叶子节点就标记为false，否则是true
（4）插入新区域：如果先不断递归找到合适区域，再求出这个区域的面积，和一般的线段树操作基本相同。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 2010; struct Node{ double x,l,r; int flag,cover; }node[maxn<<2]; struct LINE{ double x,y_up,y_down; int flag; }line[maxn]; double y[maxn]; bool cmp(LINE a,LINE b) { return a.x<b.x; } void build(int rt,int l,int r) { node[rt].l=y[l]; node[rt].r=y[r]; node[rt].flag=false; node[rt].cover=0; node[rt].x=-1; if(l+1==r) //表示一个叶子节点 { node[rt].flag=true; return ; } int mid=(l+r)>>1; build(rt<<1,l,mid); //区间是连续的。 build(rt<<1|1,mid,r); } double Insert(int rt,double x,double l,double r,int flag) { if(l>=node[rt].r||r<=node[rt].l) return 0; if(node[rt].flag) //找到一个叶节点 { if(node[rt].cover>1) //覆盖次数大于1 { double pre=node[rt].x; double ans=(x-pre)*(node[rt].r-node[rt].l); node[rt].x=x; node[rt].cover+=flag; return ans; } else { node[rt].x=x; node[rt].cover+=flag; return 0; } } double ans=0; ans+=Insert(rt<<1,x,l,r,flag); ans+=Insert(rt<<1|1,x,l,r,flag); return ans; } int main(void) { int T,i,cnt,j,n; double x1,y1,x2,y2; scanf("%d",&T); while(T--) { scanf("%d",&n); for(cnt=-1,i=0;i<n;i++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); y[++cnt]=y1; line[cnt].x=x1; line[cnt].y_down=y1; line[cnt].y_up=y2; line[cnt].flag=1; y[++cnt]=y2; line[cnt].x=x2; line[cnt].y_down=y1; line[cnt].y_up=y2; line[cnt].flag=-1; } sort(y,y+cnt+1); sort(line,line+cnt+1,cmp); build(1,0,cnt); double ans=0; for(i=0;i<=cnt;i++) { ans+=Insert(1,line[i].x,line[i].y_down,line[i].y_up,line[i].flag); } printf("%.2lf ",ans); } return 0; }