是一道扫描线的模板题，也是我的第一道扫描线的题了，对扫描线也算是有了第一次的理解，无非就是更新新的向上的区间长度，然后去查询就是了，而查询是O(1)的，因为可以通过树的最上根节点得到的。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 500;
int N, num, flag[maxN<<1], shu;
double sum[maxN<<1], X[maxN<<1];
struct node
{
double lx, rx, y;
int s;
node(double a=0, double b=0, double c=0, int d=0):lx(a), rx(b), y(c), s(d) {}
}line[maxN<<1];
bool cmp(node e1, node e2) { return e1.y < e2.y; }
inline void pushup(int rt, int l, int r) //pushup()多用，可以直接赋值时候使用
{
if(flag[rt]) sum[rt] = X[r+1] - X[l]; //如果“>0”就说明这个点是有边的
else if(l == r) sum[rt] = 0; //清零操作使用
else sum[rt] = sum[rt<<1] + sum[rt<<1|1]; //求其下的边的总和
}
inline void update(int rt, int l, int r, int ql, int qr, int val)
{
if(ql<=l && qr>=r)
{
flag[rt] += val;
pushup(myself);
return;
}
int mid = HalF;
if(ql > mid) update(QR, val);
else if(qr <= mid) update(QL, val);
else { update(QL, val); update(QR, val); }
pushup(myself);
}
inline void init()
{
num = 0; shu = 1;
memset(flag, 0, sizeof(flag));
memset(sum, 0, sizeof(sum));
}
int main()
{
int Cas = 0;
while(scanf("%d", &N) && N)
{
init();
for(int i=1; i<=N; i++)
{
double lx, ly, rx, ry;
scanf("%lf%lf%lf%lf", &lx, &ly, &rx, &ry);
line[++num] = node(lx, rx, ly, 1);
X[num] = lx;
line[++num] = node(lx, rx, ry, -1);
X[num] = rx;
}
sort(X+1, X+1+num);
sort(line+1, line+num+1, cmp);
for(int i=2; i<=num; i++) if(X[i] != X[i-1]) X[++shu] = X[i];
double ans = 0;
for(int i=1; i<num; i++) //离散化更新的过程
{
int l = (int)(lower_bound(X+1, X+shu+1, line[i].lx) - X);
int r = (int)(lower_bound(X+1, X+shu+1, line[i].rx) - X - 1);
update(1, 1, shu, l, r, line[i].s);
ans += sum[1] * (line[i+1].y - line[i].y);
}
printf("Test case #%d\n", ++Cas);
printf("Total explored area: %.2lf\n\n", ans);
}
return 0;
}
/*
2
15 15 25 25.5
10 10 20 20
ans:180
5
1.37 0.10 2.75 0.20
2.96 2.01 3.06 2.75
2.65 1.05 4.97 1.15
2.33 0.74 4.02 0.84
2.96 0.10 4.02 1.47
ans:1.85
8
9.33 19.52 30.44 24.39
8.06 29.38 9.75 51.77
22.38 15.06 32.35 33.30
30.66 19.20 44.13 19.62
17.93 15.38 39.35 41.58
9.65 6.47 29.80 10.39
26.20 24.61 40.63 35.85
25.25 12.51 29.80 36.17
ans:751.10
*/
