POJ_1151 扫描线+离散化+线段树

学线段树的时候学的扫描线（虽然早就看过了，一直没敲过，还是懒），现在来补一道题：

因为题目给的矩形的坐标是浮点型的，所以毫无疑问要离散化，我们以y轴坐标来建立线段树（当然也可以以x轴，这样的话扫描线是上下方向的了），然后Line表示扫描线的下一个位置。求面积的就是ans+=(line[i].x-line[i-1].x)*tree[1].cnt。其实说白了扫描线就是一个区间操作的线段树：不过节点存的是c（这个整个的区间被覆盖的次数，如果为0，则：这个整区间未被完全覆盖）,cnt是整个区间所覆盖的长度。每次只需要更新这两个值就好了，设矩形的左边的权值是1，右边的权值是-1，每一条边覆盖是，总是带着权值覆盖的。

一开始搞成了一个简单的pushup，pushdown操作（可能是两个操作都写挫了）后来发现这样写一直wa，看了kuangbin的博客才知道：这里不需要pushdown，因为矩形的边总是对称的，也就是说并不需要pushdown，等对应边进来的时候直接就把对应加上去的次数给减了（如果强行pushdown，那么下次寻找的时候必须要每次找到叶子节点,复杂度就上去了），不用pushdown的另外一个好处就是pushup比较好写，蠢蠢地wa了三次以后，照着bin神的代码改了才ac了：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll  long long
#define lrt rt<<1
#define rrt rt<<1|1
#define lson    rt<<1,l,mid
#define rson    rt<<1|1,mid+1,r
#define FOR(i,x,y)  for(int i = x;i < y;i ++)

using namespace std;

const int MAXN = 111<<1;

struct Line{
    double x,y1,y2;
    int f; //记录边是左边还是右边
}line[MAXN];

struct Tree{
    int l,r;
    int c;  //用来记录该区间被矩形包含的次数
    double cnt,lf,rf;   //cnt用来记录矩形实际包含扫描线的长度,lf,rf分别保存这个区间左右的边的浮点值
}tree[MAXN<<2];

bool cmp(Line a,Line b){
    return a.x < b.x;
}

double y[MAXN];//用来记录所有点的y坐标

void Build(int rt,int l,int r){
    tree[rt].l = l; tree[rt].r = r;
    tree[rt].c = 0; tree[rt].cnt = 0;
    tree[rt].lf = y[l]; tree[rt].rf = y[r];
    if(l+1 == r)    return;
    int mid = (l+r)>>1;
    Build(lrt,l,mid);
    Build(rrt,mid,r);
}

void pushup(int t)
{
    if(tree[t].c>0)
    {
        tree[t].cnt=tree[t].rf-tree[t].lf;
        return;
    }
    if(tree[t].l+1==tree[t].r)  tree[t].cnt=0;
    else  tree[t].cnt=tree[t<<1].cnt+tree[t<<1|1].cnt;
}

void Modify(int rt,Line e){
    if(tree[rt].lf == e.y1 && tree[rt].rf == e.y2){
        tree[rt].c += e.f;
        pushup(rt);
        return;
    }
    int mid = (tree[rt].l+tree[rt].r)>>1;
    if(e.y2 <= y[mid])  Modify(lrt,e);
    else if(e.y1 >= y[mid]) Modify(rrt,e);
    else{
        Line tem = e;
        tem.y2 = y[mid];
        Modify(lrt,tem);
        tem = e;
        tem.y1 = y[mid];
        Modify(rrt,tem);
    }
    pushup(rt);
}

int main()
{
    freopen("test.in","r",stdin);
    int n,t,tCase = 0;
    double x1,y1,x2,y2;
    while(scanf("%d",&n),n){
        t = 1;
        FOR(i,1,n+1){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            line[t].x = x1;
            line[t].y1 = y1;
            line[t].y2 = y2;
            line[t].f = 1;
            y[t] = y1;
            t++;
            line[t].x = x2;
            line[t].y1 = y1;
            line[t].y2 = y2;
            line[t].f = -1;
            y[t] = y2;
            t++;
        }
        sort(line+1,line+t,cmp);
        sort(y+1,y+t);
        Build(1,1,t-1);
        double ans = 0;
        Modify(1,line[1]);
        FOR(i,2,t){
            ans += tree[1].cnt*(line[i].x-line[i-1].x);
            Modify(1,line[i]);
        }
        printf("Test case #%d
Total explored area: %.2f

",++tCase,ans);
    }
    return 0;
}