POJ 1151 / hdu 1828 矩形面积并 扫描线+线段树

• 应将线段树存储区间对应于矩形边的区段。

/*
 * File:   main.cpp
 * Author: semprathlon
 *
 * Created on April 9, 2016, 10:19 AM
 */

#include 
#include 
#include 
#include 
#include 

using namespace std;

struct Rectangle{
    double x1,y1,x2,y2;
    Rectangle(){}
    Rectangle(double _x1,double _y1,double _x2,double _y2):x1(_x1),x2(_x2),y1(_y1),y2(_y2){}
};

vector rects;
vector ys;

struct SegTree{
    SegTree *lchild,*rchild;
    int l,r,m;
    double s;
    int w;
    SegTree(){}
    SegTree(int _l,int _r):l(_l),r(_r){
        m=(l+r)>>1;w=0;s=0;
        if (l0)
        s=lchild->s+rchild->s;
    }
    void down(){
        if (w>0){
            lchild->w+=w;
            rchild->w+=w;
            if (lchild->w)
                lchild->s=ys[lchild->r+1]-ys[lchild->l];
            if (rchild->w)
                rchild->s=ys[rchild->r+1]-ys[rchild->l];
            s=w=0;
        }
    }
    void modify(int x,int y,int v){
        if (l==r){
            w+=v;
            if (w>0)
                s=ys[r+1]-ys[l];
            else
                s=0;
            return;
        }
        if (x==l&&r==y){
            w+=v;
            if (w>0){
                s=ys[r+1]-ys[l];
                return;
            }
            else
                s=0;
        }
        down();
        if (x<=m)
            lchild->modify(x,min(m,y),v);
        if (y>m)
            rchild->modify(max(m+1,x),y,v);
        up();
    }
    double query(int x,int y){
        //cout<<"q "<0?s:0;
        if (x==l&&r==y&&w>0){
            return s;
        }
        down();
        double res=0;
        if (x<=m) res+=lchild->query(x,min(m,y));
        if (y>m) res+=rchild->query(max(m+1,x),y);
        up();
        return res;
    }
} *T;

bool cmp(const double& a,const double& b){
    if (abs(a-b)<1e-5)
        return 0;
    return a-b<0;
}

double unionArea(const vector& rects){
    if (rects.empty()) return 0;
    typedef pair > Event;
    vector events;
    ys.clear();
    for(int i=0;i cnt(ys.size()-1,0);
    for(int i=0;iy2) swap(y1,y2);
        T->modify(y1,y2-1,delta);
        //for(int j=0;jquery(j,j);
            //cout<query(j,j)<query(0,ys.size()-2);
//        cout<>n){
        if (!n) break;
        rects.clear();
        for(int i=0;i>x1>>y1>>x2>>y2;
            rects.push_back(Rectangle(x1,y1,x2,y2));
        }
        cout<<"Test case #"<<++cas<