题意：
给出n个矩形的左下角和右上角坐标，求这n个矩形所构成的面积
思路：
线段树扫描线
这是第一次做到线段树扫描线，刚开始也不懂
如果不懂，可以看：
和
我是看第一个链接弄懂的 然后学习了第二位的方法
代码上也有比较详细的注释，想可以帮到大家
code：
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<vector>#include<queue>using namespace std;const int maxn = 205;struct Line{double x;//存的是线段的x坐标double y1,y2;//存的是线段的下、上两个端点double f;//f是用来记录重叠情况的，，可以根据这个来计算node中的c}line[maxn*2];//把一段段平行于y轴的线段表示成数组，//x是线段的x坐标，y1 y2是线段对应的下端点和上端点//一个矩形，左侧的边的f = 1,右侧的边 f= -1//f是用来记录重叠情况的，可以根据这个来计算node中的cdouble y[maxn*2];//用来记录y坐标，排序之后用来给线段树中的左右实际结点赋值，见代码build部分//线段树的节点总数，大概要是线段个数的 4 倍（线段树和被操作的数据之间总是四倍关系）const int maxnode = maxn << 2;struct IntervalTree{double ll[maxnode],rr[maxnode],lf[maxnode],rf[maxnode],cnt[maxnode];//ll[]和rr[] 是用来标记线段树某一个区间的 经过离散化之后的 可以投影到实际坐标的 那个左右整点代号//lf rf 是用来记录真正的左右坐标的，用来计算该区间的长度int c[maxnode];//c是用来标记重叠情况的void build(int o, int l, int r){//递归建线段树ll[o] = l, rr[o] = r;cnt[o] = c[o] = 0;lf[o] = y[l], rf[o] = y[r];int mid = (l+r)>>1;int lc = o << 1, rc = o << 1 | 1;if(l + 1 == r) return;build(lc, l, mid);build(rc, mid, r);}void calen(int o){//用来计算区间o中的 线段被覆盖的长度if(c[o] > 0){cnt[o] = rf[o] – lf[o];return;}if(ll[o] + 1 == rr[o]) cnt[o] = 0;else{cnt[o] = cnt[o<<1] + cnt[o<<1|1];}}void update(int o, Line e){//新加入一条线段后 更新线段树double y1 = e.y1, y2 = e.y2;if(lf[o] == y1 && y2 == rf[o]){c[o] += e.f;calen(o);return;}int lc = o << 1, rc = o<<1|1;if(y2 <= rf[lc]) update(lc, e);else if(y1 >= lf[rc]) update(rc, e);else{Line tmp = e;tmp.y2 = rf[lc];update(lc, tmp);tmp = e;tmp.y1 = lf[rc];update(rc, tmp);}calen(o);}}tree;bool cmp(Line a, Line b){return a.x < b.x;}int main(){int n;int cas = 0;while(scanf("%d",&n) != EOF){if(n == 0) break;double y1,y2,x1,x2;int t = 1;for(int i = 1; i <= n; i++){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);//这是一个处理和保存矩形左右两条边，并且对坐标进行离散化的过程//一个矩形 对应的是两条线段，左面一条（f = 1）右面一条(f = -1)line[t].x = x1;line[t].y1 = y1;line[t].y2 = y2;line[t].f = 1;y[t] = y1;t++;line[t].x = x2;line[t].y1 = y1;line[t].y2 = y2;line[t].f = -1;y[t] = y2;t++;}sort(y+1, y+t);//对y坐标按照从小到大的顺序排序，这是为了建立线段树，排完序才能离散地分成许多个区间sort(line+1, line+t, cmp);//从左到右扫描的话，应该保证在左边的线段先被扫到，//这里的排序就是让左边的线段在前面（按照x坐标从小到大排序）double res = 0;tree.build(1,1,t-1);//每扫描到一条上下边后并投影到总区间后，就判断总区间现在被覆盖的总长度，然后用下一条边//的高度减去当前这条边的高度，乘上总区间被覆盖的长度，就能得到一块面积，并依此做下去，//就能得到最后的面积。tree.update(1,line[1]);//先扫地一条边for(int i = 2; i < t; i++){res += tree.cnt[1] * (line[i].x – line[i-1].x);//用 高度*覆盖长度tree.update(1, line[i]);//扫描当前边}printf("Test case #%d\nTotal explored area: %.2f\n\n",++cas,res);}return 0;}
生活会变成什么样子?正因为时光流逝一去不复返，
