扫描法+线段树

题意

二维平面有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\nTotal explored area: %.2lf\n\n",++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就很好理解了 
*/

扫描法+线段树

原文：https://www.cnblogs.com/tyner/p/11231256.html