算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

    给出很多矩形,求矩形并的面积。

吐槽:

    1. 经过傻崽大神的教诲,我决定不再向以前那样恶意缩短代码了
    2. 看来.... 要慢慢改...
    3. 思路仍然是按照傻崽大神的blog写的... 然后转成了zkw版线段树...

思路分析:

    离散化之后,在脑海中想像一个扫描线,按照y轴从小到大的顺序扫过去。
    扫到的肯定是一个x轴的区间集合。 如果遇到了“新边”就加到集合中,遇到“旧边”就从集合中减去,每一次需要这样操作的时候我们就称之为“事件点”。
    每次遇到事件点的时候,我们就计算一次面积。就是与下个事件点的y的距离乘以这个区间集合的总长度就可以了。
    那么维护这个集合就可以用线段树了。
    每次遇到新边就cnt++,否则就cnt--。如果cnt不为0,说明这个节点有边覆盖...
    感觉还是朴素版更容易理解一些,写起来很飘逸~
#include<iostream>
#include<cstdio>
#include<cassert>
#include<algorithm>
using namespace std;
const int V = 400;
int M,len;
struct segment_tree{
    int cnt; double sum;
} seg[V<<2];
struct segment{
    double l,r,y; int flag;
    segment(double x1=0,double x2=0,double y1=0,int p=0):l(x1),r(x2),y(y1),flag(p){}
} num[V];
bool operator < (segment a,segment b){
    return a.y< b.y;
}
double X[V],sum[V<<2];
inline void upt(int x){
    if(seg[x].cnt) seg[x].sum = sum[x];
    else if(x<M) seg[x].sum = seg[x<<1].sum+seg[x<<1|1].sum;
    else seg[x].sum=0;
}
double insert(int l,int r,int p){
//    cout<<l<<" "<<r<<" "<<p<<endl;
    for(l = l+M, r = r+M+2; l^r^1 ; l>>=1 , r>>=1){
        if(l&1^1){ seg[l^1].cnt += p; upt(l^1); }
        if(r&1){ seg[r^1].cnt += p; upt(r^1); }
        upt(l);upt(r);
    }
    upt(r);
    while(l){
        upt(l);    l >>=1;
    }
//    cout<<seg[1].sum<<endl;
    return seg[1].sum;
}
int search(double val){
    int l = 0, r = len;
    while(l<r){
        int mid = l+r >>1;
        if(X[mid]>= val) r = mid;
        else l = mid+1;
    }
    return r;
}
void build_tree(int n){
    for(int i=0;i<30;i++) if((1<<i) > n+1) {
            M = 1<<i; break;
    }
    for(int i=0;i<M*2;i++) sum[i] = seg[i].cnt = seg[i].sum = 0;
    for(int i=0;i<n-1;i++) sum[i+M+1] = X[i+1]-X[i];
    for(int i=M-1;i;i--) sum[i] = sum[i<<1]+sum[i<<1|1];
}
int main(){
    int n,__test=1;
    while(scanf("%d",&n)!=-1 && n){
        double x1,y1,x2,y2;
        int N = 0;
        for(int i =0 ;i<n;i++){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            X[N] = x1;
            num[N++] = segment(x1,x2,y1,1);
            X[N] = x2;
            num[N++] = segment(x1,x2,y2,-1);
        }
        sort(X,X+N);
        sort(num,num+N);
        len = 1;
        for(int i=1;i<N;i++){    
            if(X[i]!=X[i-1]) X[len++] = X[i];
        }
        build_tree(len);
        double ans = 0;
        for(int i=0;i<N-1;i++){
            int l = search(num[i].l);
            int r = search(num[i].r)-1;
            ans += insert(l,r,num[i].flag) * (num[i+1].y - num[i].y);
//            cout<<ans<<endl;
        }
//        cout<<ans<<endl;
        printf("Test case #%d\nTotal explored area: %.2lf\n\n",__test++, ans);
    }
    return 0;
}
posted on 2012-05-08 16:49 西月弦 阅读(726) 评论(0)  编辑 收藏 引用 所属分类: 解题报告经典题目

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理