题意

给你n个矩形，算出他们覆盖了多少面积

思路

总结一下扫描线的套路
把矩形的上下边 按照 左端点的x坐标 右端点的x坐标 高度 为上位边还是下位边存起来
当作扫描线 根据高度排序，从低到高，也就是y坐标
把所有x坐标都提取出来 排序离散化
线段树维护的节点 为x坐标某个区间内左端点 右端点 下位边的总长度 下位边的数量
如果扫描线下标为1~m 循环1 ~ m-1
m条扫描线 循环m-1次 每次先更新当前下位边总长度 算出当前扫描线与下一条扫描线的差值*当前下位边总长度 即为两条扫描线覆盖的面积
学习自某位dalao博客的扫描线思想

AC_code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 205;
struct node {
	double l, r, h;//左端点 右端点 高度
	int d;
	//标记上位边 还是下位边
	//1为下位边 -1为上位边
	node() {}
	node(double l,double r, double h, int d):l(l),r(r),h(h),d(d) {}
	bool operator < (const node &a)const {
		return h<a.h;
	}
} line[maxn]; //扫描线

double x[maxn];//离散化过的x坐标
int cnt[maxn<<2];//标记某个区间下位边数量
double sum[maxn<<2];//标记某个区间下位边长度

//更新的节点 更新的左端点 更新的右端点
void pushup(int i,int l,int r) {
	if(cnt[i]) {
		sum[i] = x[r+1] - x[l];
	} else {
		sum[i] = sum[i<<1] + sum[i<<1|1];
	}
}

// 更新的区间左端点 更新的区间右端点 增加的下位边的数量 更新的节点 更新到的左端点 更新到的右端点
void update(int ql, int qr, int v, int i, int l, int r) {
	if(ql <= l && qr >= r) {
		cnt[i] += v;
		pushup(i, l, r);
		return;
	}
	int mid = (l + r) / 2;
	if(ql <= mid) {
		update(ql, qr, v, i<<1, l, mid);
	}
	if(qr > mid) {
		update(ql, qr, v, i<<1|1, mid+1, r);
	}
	pushup(i, l, r);
}
int main() {
	int cas = 1;
	int t;
	while(~scanf("%d",&t)) {
		if(t == 0) {
			break;
		}
		memset(cnt, 0, sizeof(cnt));
		memset(sum, 0, sizeof(sum));//初始化 相当于bulid_tree
		int n = 0, m = 0;
		double x1, x2, y1, y2;
		for(int i = 0; i < t; i++) {
			scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
			x[++n] = x1;
			x[++n] = x2;
			line[++m] = node(x1, x2, y1, 1);//下位边
			line[++m] = node(x1, x2, y2, -1);//上位边
		}
		sort(x+1, x+1+n);
		sort(line+1, line+1+m);
		int k = unique(x+1, x+n+1) - x - 1;//离散化
		double ans = 0.0;
		for(int i = 1; i < m; i++) { //m条扫描线 循环m-1次即可 
			int l = lower_bound(x+1, x+k+1, line[i].l) - x;
			int r = lower_bound(x+1, x+k+1, line[i].r) - x - 1;//这里记得减1
			if(l <= r) {
				update(l, r, line[i].d, 1, 1, k-1);
			}
			//sum[1]代表总的下位边长度 
			ans += sum[1] * (line[i+1].h - line[i].h); 
		}
		printf("Test case #%d\nTotal explored area: %.2f\n\n", cas++, ans);
	}
	return 0;
}