这里是简介
题意
给定$n$个矩形$(x_1,y_1,x_2,y_2)$，求这$n$个矩形的面积并
题解
扫描线裸题，可以不用线段树维护，$O(n^2)$是允许的。
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::sort;
using std::unique;
using std::lower_bound;
const int N = 1e2 + 10;
int n, m, tot;
double ans, x1[N], y1[N], x2[N], y2[N], raw[N << 1], tmp[N << 1];
struct Node {
double x, dy, uy, g;
inline bool operator < (const Node &a) const { return x < a.x; }
} cy[N << 1]; int cnt;
double val[N << 3]; int fg[N << 3];
inline void update(int o, int l, int r) {
if(fg[o]) val[o] = raw[r + 1] - raw[l];
else if(l == r) val[o] = 0;
else val[o] = val[o << 1] + val[o << 1 | 1];
}
void modify (int ml, int mr, int k, int o = 1, int l = 1, int r = m) {
if(l >= ml && r <= mr) {
fg[o] += k, update(o, l, r);
return ;
}
int mid = (l + r) >> 1, lc = o << 1, rc = lc | 1;
if(ml <= mid) modify(ml, mr, k, lc, l, mid);
if(mr > mid) modify(ml, mr, k, rc, mid + 1, r);
update(o, l, r);
}
int main () {
while(scanf("%d", &n) != EOF) {
if(!n) break; ++tot; ans = m = cnt = 0;
memset(val, 0, sizeof val), memset(fg, 0, sizeof fg);
for(int i = 1; i <= n; ++i) {
scanf("%lf%lf%lf%lf", x1 + i, y1 + i, x2 + i, y2 + i);
tmp[++m] = y1[i], tmp[++m] = y2[i];
}
sort(&tmp[1], &tmp[m + 1]); m = unique(&tmp[1], &tmp[m + 1]) - tmp - 1;
for(int i = 1; i <= n; ++i) {
int ind1 = lower_bound(&tmp[1], &tmp[m + 1], y1[i]) - tmp;
int ind2 = lower_bound(&tmp[1], &tmp[m + 1], y2[i]) - tmp;
raw[ind1] = y1[i], raw[ind2] = y2[i], y1[i] = ind1, y2[i] = ind2;
}
for(int i = 1; i <= n; ++i) {
cy[++cnt] = (Node){x1[i], y1[i], y2[i], 1};
cy[++cnt] = (Node){x2[i], y1[i], y2[i], -1};
} sort(&cy[1], &cy[cnt + 1]);
for(int i = 1; i <= cnt; ++i) {
modify(cy[i].dy, cy[i].uy - 1, cy[i].g);
ans += val[1] * (cy[i + 1].x - cy[i].x);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n", tot, ans);
}
return 0;
}