题意：给出多个矩形的左上角和右下角坐标，求这些矩形面积的并，即相重的面积只算一次
解题思路：
首先离散化：把读进来的坐标变为一条竖边，一个矩形有两个竖边：左竖边和右竖边，左竖边用与制造覆盖，右竖边用于消除覆盖，要标记好哪些是左竖边，哪些是右竖边。建一个结构体数组来存放竖边，并按照竖边的很坐标升序排序（从小到大）。把所有的纵坐标用一个数组存放，并升序排序，离散化结束。建一个线段树用于查看目前那些纵坐标被覆盖了，从而计算当前的被覆盖纵坐标长度。结合竖边的左右性质就能不断更新线段树，从而计算新的矩形。
数据很水。0msC++代码
#include#include #include #include #include #include using namespace std;const int NUM = 100005;typedef struct line{int x,y1,y2,flag;};typedef struct node{int left,mid,right,key,len;}node;line lines[NUM];node T[ NUM<<2 ];int Y[NUM];//存储离散化的纵坐标void create(int u,int l,int r){T[u].left = l;T[u].right = r;T[u].key = 0;T[u].len = 0;T[u].mid = (l+r)>>1;if(r == l + 1)return;create(u+u,l,T[u].mid);create(u+u+1,T[u].mid,r);}int inquiry(int i){if(T[i].key > 0) //有覆盖{return (T[i].len = Y[T[i].right] - Y[T[i].left]);}else if (T[i].right - T[i].left == 1){return (T[i].len = 0);}// 其他情况else{return (T[i].len = T[i+i].len + T[i+i+1].len);}}void change(line li,int i)//order为要修改的序号{if (Y[T[i].left] == li.y1 && Y[T[i].right] == li.y2){// “左”边flag是1 “右”边flag是-1// 其实是计算完一个矩形的面积之和，key减去1// 就相当于把这个矩形擦除掉了T[i].key += li.flag;}else{int m = (T[i].left + T[i].right) >> 1;if (li.y1 >= Y[m]){change(li, i+i+1);}else if (li.y2 <= Y[m]){change(li, i+i);}else{line ll, lr;ll.y1 = li.y1;ll.y2 = Y[m];ll.flag = li.flag;lr.y1 = Y[m];lr.y2 = li.y2;lr.flag = li.flag;change(ll, i+i);change(lr, i+i+1);}}// 每次插入节点后，计算覆盖的长度inquiry(i);}bool cmp(const line& lhs, const line& rhs){return lhs.x < rhs.x;}int main(){int x1,y1,x2,y2,end=0,n;while(1){int i = 1;while(scanf("%d %d %d %d",&x1,&y1,&x2,&y2)){if(x1 == -1 && x2 == -1 && y1 == -1 && y2 == -1)break;if(x1 == -2 && x2 == -2 && y1 == -2 && y2 == -2){end = 1;break;}if (y1 > y2){swap(y1, y2);}// 左边的边横坐标是x1，所以x1必须是小的一个if (x1 > x2){swap(x1, x2);}lines[i].x = x1;lines[i].y1 = y1;lines[i].y2 = y2;lines[i].flag = 1;Y[i++] = y1;lines[i].x = x2;lines[i].y1 = y1;lines[i].y2 = y2;lines[i].flag = -1; // 抵消上次的覆盖Y[i++] = y2;}n = i-1;sort(Y+1,Y+n+1);sort(lines+1,lines+n+1,cmp);create(1,1,n);change(lines[1],1);int ans = 0;for(i = 2; i <= n ; i++){ans += T[1].len * (lines[i].x - lines[i-1].x);change(lines[i],1);}printf("%d\n", ans);if(end)break;}return 0;}