解题报告

题目传送门

题意：

求矩形并面积。

思路：

离散+线段树+扫描线。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
struct Seg {
    int v;
    double h,lx,rx;
    friend bool operator < (Seg a,Seg b) {
        return a.h<b.h;
    }
} seg[4000];
struct R {
    double lx,ly,rx,ry;
} re[1100];
int lz[401000];
double _hash[101000],sum[401000];
void push_up(int rt,int l,int r) {
    if(lz[rt])sum[rt]=_hash[r+1]-_hash[l];
    else if(l==r)sum[rt]=0;
    else
        sum[rt]=sum[rt*2]+sum[rt*2+1];
}
void update(int rt,int l,int r,int ql,int qr,int v) {
    if(ql>r||qr<l)return;
    if(ql<=l&&r<=qr) {
        lz[rt]+=v;
        push_up(rt,l,r);
        //sum[rt]+=_hash[r+1]-_hash[l];
        return ;
    }
    int mid=(l+r)/2;
    update(rt*2,l,mid,ql,qr,v);
    update(rt*2+1,mid+1,r,ql,qr,v);
    push_up(rt,l,r);
}
int main() {
    int n,i,j,k=1;
    while(~scanf("%d",&n)) {
        if(!n)break;
        int cnt=0;
        memset(lz,0,sizeof(lz));
        memset(sum,0,sizeof(sum));
        double ans=0;
        for(i=0; i<n; i++) {
            scanf("%lf%lf%lf%lf",&re[i].lx,&re[i].ly,&re[i].rx,&re[i].ry);
            _hash[i]=re[i].lx;
            _hash[i+n]=re[i].rx;
            seg[cnt].h=re[i].ly;
            seg[cnt].lx=re[i].lx;
            seg[cnt].rx=re[i].rx;
            seg[cnt++].v=1;
            seg[cnt].h=re[i].ry;
            seg[cnt].lx=re[i].lx;
            seg[cnt].rx=re[i].rx;
            seg[cnt++].v=-1;
        }
        sort(seg,seg+cnt);
        sort(_hash,_hash+n*2);
        int m=unique(_hash,_hash+n*2)-_hash;
        for(i=0; i<cnt-1; i++) {
            int l=lower_bound(_hash,_hash+m,seg[i].lx)-_hash;
            int r=lower_bound(_hash,_hash+m,seg[i].rx)-_hash-1;
            update(1,0,m-1,l,r,seg[i].v);
            ans+=sum[1]*(seg[i+1].h-seg[i].h);
        }
        printf("Test case #%d\nTotal explored area: ",k++);
        printf("%.2lf\n",ans);
        printf("\n");
    }
    return 0;
}

Atlantis

2
10 10 20 20
15 15 25 25.5
0

Test case #1
Total explored area: 180.00 

HDU1542_Atlantis(扫描线/线段树+离散),布布扣,bubuko.com

HDU1542_Atlantis(扫描线/线段树+离散)

原文：http://blog.csdn.net/juncoder/article/details/38499615