题意：给n个可能相交的矩形，问你不重复的总面积
思路：扫描线，一边扫一边加。
扫描线：图片来源：理解扫描线
假设我们要算以下四个矩形面积，显然中间深色的是重复的。我们按照x的大小，从左往右扫，然后用线段树维护y轴向的长度就可以了。但是，我们不能用点去维护y轴坐标，而是抽象成把点i看成y[i]到y[i+1]这个区间，不然会有错。
代码：
#include<set> #include<map> #include<stack> #include<cmath> #include<queue> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<sstream> #include<iostream> #include<algorithm> typedef long longll; using namespace std; const int maxn = 100 + 10; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; struct Bian{ double x, y1, y2; int flag; bool operator < (const Bian &a) const{ return x < a.x; } }bian[maxn << 1]; double y[maxn << 1]; //离散化定位 int n, cnt; int Find(double x){ //在y中离散化后位置 int l = 1, r = cnt, ans = 0; while(l <= r){ int m = (l + r) >> 1; if(fabs(y[m] - x) < 1e-7) ans = m; if(y[m] > x) r = m - 1; else l = m + 1; } return ans; } int cover[maxn << 3]; //y的覆盖次数 double sum[maxn << 3]; void pushUp(int l, int r, int rt){ if(cover[rt] > 0) sum[rt] = y[r + 1] - y[l]; //全覆盖了 else if(l == r) sum[rt] = 0; //没覆盖的叶子结点 else sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; //部分覆盖 } void build(int l, int r, int rt){ if(l == r){ cover[rt] = sum[rt] = 0; return; } int m = (l + r) >> 1; build(l, m, rt << 1); build(m + 1, r, rt << 1 | 1); cover[rt] = sum[rt] = 0; } void update(int L, int R, int l, int r, int v, int rt){ if(L <= l && R >= r){ cover[rt] += v; pushUp(l, r, rt); return; } int m = (l + r) >> 1; if(L <= m) update(L, R, l, m, v, rt << 1); if(R > m) update(L, R, m + 1, r, v, rt << 1 | 1); pushUp(l, r, rt); } int main(){ int ca = 1; while(scanf("%d", &n) && n){ for(int i = 1; i <= n; i++){ double x1, x2, y1, y2; scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); int ll = 2 * i - 1, rr = 2 * i; bian[ll].x = x1, bian[ll].y1 = y1, bian[ll].y2 = y2; bian[ll].flag = 1; bian[rr].x = x2, bian[rr].y1 = y1, bian[rr].y2 = y2; bian[rr].flag = -1; y[ll] = y1, y[rr] = y2; //定位用的 } n = n + n; sort(bian + 1, bian + n + 1); sort(y + 1, y + n + 1); cnt = 1; //unique for(int i = 2; i <= n; i++){ if(y[i] != y[i - 1]){ y[++cnt] = y[i]; } } double ans = 0; build(1, cnt, 1); for(int i = 1; i < n; i++){ update(Find(bian[i].y1), Find(bian[i].y2) - 1, 1, cnt, bian[i].flag, 1); ans += sum[1] * (bian[i + 1].x - bian[i].x); } printf("Test case #%d ", ca++); printf("Total explored area: %.2lf ", ans); } return 0; }