题意：
有n个矩形，求出总面积（面积并），矩形之间有可能重合。
思路：
这道题的目的是求出面积的并，因为有重合的部分所以常规方式不行。 扫描线法：想像一条平行于y轴的线，从x最小开始向右扫描，扫描出的面积就是总 面积。 看起来很简单，实现起来是用到了线段树维护y的长度，长度怎么维护？ 将平行于y轴的线段依次插入线段树中，线段树保存当前的len。 离散化y[]的目的是方便于建树。把坐标y的大小缩小到了1~t-1之中。
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; #define L(x) (x<<1) #define R(x) (x<<1|1) struct Line { double x,y1,y2; int flag; }line[500]; struct Node { int l,r,cover; double lf,rf,len; }node[2000]; double y[2000]; bool cmp(Line a,Line b) { return a.x < b.x; } void build(int u,int l,int r) { node[u].l = l;node[u].r = r; node[u].lf = y[l];node[u].rf = y[r]; node[u].len = node[u].cover = 0; if(l+1 == r) return ; int mid = (l+r)>>1; build(L(u),l,mid); build(R(u),mid,r); } void length(int u) { if(node[u].cover > 0) { node[u].len = node[u].rf - node[u].lf; return ; } else if(node[u].l + 1 == node[u].r) { node[u].len = 0; } else node[u].len = node[L(u)].len + node[R(u)].len; } void update(int u,Line e) { if(e.y1 == node[u].lf && e.y2 == node[u].rf) { node[u].cover += e.flag; length(u); return ; } if(e.y1 >= node[R(u)].lf) update(R(u),e); else if(e.y2 <= node[L(u)].rf) update(L(u),e); else { Line temp = e; temp.y2 = node[L(u)].rf; update(L(u),temp); temp = e; temp.y1 = node[R(u)].lf; update(R(u),temp); } length(u); } int main() { //freopen("in.txt","r",stdin); int n,t,i,Case = 0; double x1,y1,x2,y2,ans; while(scanf("%d",&n) != EOF && n) { for(i = t = 1;i <= n; i++,t++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); line[t].x = x1; line[t].y1 = y1; line[t].y2 = y2; line[t].flag = 1; y[t++] = y1; line[t].x = x2; line[t].y1 = y1; line[t].y2 = y2; line[t].flag = -1; y[t] = y2; } sort(line+1,line+t,cmp); sort(y+1,y+t); build(1,1,t-1); update(1,line[1]); ans = 0; for(i = 2;i < t; i++) { ans += node[1].len*(line[i].x-line[i-1].x); update(1,line[i]); } printf("Test case #%d\n",++Case); printf("Total explored area: %.2f\n\n",ans); } return 0; }