题意
二维平面有n个平行于坐标轴的矩形,现在要求出这些矩形的总面积. 重叠部分只能算一次.
分析:
线段树的典型扫描线用法.
参考博客
https://blog.csdn.net/xianpingping/article/details/83032798
请思考后下翻（虽然遮不住
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 400+99
int n;
double sumv[MAX<<2];
int cnt[MAX<<2];
double hack[MAX];
//以横坐标作为线段(区间),对横着的线段进行扫描
//扫描的作用是每次更新下底边总长度和下底边个数,增加新面积
struct seg{
double l, r, h;
int d;
seg(){}
seg(double l, double r, double h, int d) : l(l), r(r), h(h), d(d) {}
bool operator < (const seg& xxx) const {
return h < xxx.h ;
}
}s[MAX];
void push_up(int o, int l, int r) {//更新sumv（这里的hack需要用到l和r
if(cnt[o]) sumv[o] = hack[r+1] - hack[l];//o的区间所表示的整个线段都可以作为底边
else if(l == r) sumv[o] = 0;//叶子结点表示[x,x)，它的区间长度为0
else sumv[o] = sumv[o<<1] + sumv[o<<1|1];
}
void optadd(int o, int l, int r, int ql, int qr, int d) {
if(ql <= l && r <= qr) {
cnt[o] += d;//更新
push_up(o, l, r);
return ;
}
int mid = (l + r) >> 1;
if(ql <= mid) optadd(o<<1, l, mid, ql, qr, d);
if(mid < qr) optadd(o<<1|1, mid+1, r, ql ,qr, d);
push_up(o, l, r);
}
int search(double key, double *x, int n) {//在
int l = 0, r = n - 1;
while(l <= r) {
int mid = (l + r) >> 1;
if(x[mid] == key) return mid;
if(x[mid] > key) r = mid - 1;
else l = mid + 1;
}
return -1;//也可以不写，但这样逻辑上过得去
}
int main() {
double x1, x2, y1, y2;
int num = 0;
while(cin>>n , n) {
int k = 0;
for(int i = 0; i < n; i++) {
cin>>x1>>y1>>x2>>y2;
hack[k] = x1;
s[k++] = seg(x1, x2, y1, 1);
hack[k] = x2;
s[k++] = seg(x1, x2, y2, -1);
}
sort(s, s+k);
sort(hack, hack+k);//离散化
int tot = 0;
for(int i = 1; i < k; i++) if(hack[i] != hack[tot]) hack[++tot] = hack[i];
double ans = 0;
//cnt 会在这清零
tot++;//tot在上面是从零开始数组的坐标，现在是大小
for(int i = 0; i < k; i++) {//开始扫描
int L = search(s[i].l , hack, tot);
int R = search(s[i].r , hack, tot) - 1;//左闭右开
optadd(1, 0, tot-1, L, R, s[i].d );//querysum操作，顺便更新底边长度和底边相差个数
ans += sumv[1] * (s[i+1].h - s[i].h );//新增面积
}
printf("Test case #%d
Total explored area: %.2lf
",++num,ans);
}
}/*
这里注意下扫描线段时r-1:int R=search(s[i].l,hack,m)-1;
计算底边长时r+1:if(mark[n])sum[n]=hack[right+1]-hack[left];
解释:假设现在有一个线段左端点是l=0,右端点是r=m-1
则我们去更新的时候,会算到sum[1]=hack[mid]-hack[left]+hack[right]-hack[mid+1]
这样的到的底边长sum是错误的,why?因为少算了mid~mid+1的距离,由于我们这利用了
离散化且区间表示线段,所以mid~mid+1之间是有长度的,比如hack[3]=1.2,hack[4]=5.6,mid=3
所以这里用r-1,r+1就很好理解了
*/