记录编号	562541	评测结果	AAAAAAAAAA
题目名称	[POJ 1151]亚特兰蒂斯	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	2.536 s
提交时间	2021-07-06 15:32:40	内存使用	14.40 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;
int n,tot = 0;
double ans = 0;
int cnt = 0;
double w[maxn << 1];
int ls[maxn << 2],rs[maxn << 2];//左右边界 
double len[maxn << 2],cover[maxn << 2];//当前已被覆盖的长度（无重复），当前被覆盖的总长度（有重复）
//整个扫描线上被覆盖的长度即为根节点的len值 
//对于叶子结点i，cover[i]=1表示[i,i+1]的区间中有覆盖 
struct scanline {
    double x,y1,y2;
    //横坐标，上下纵坐标 
    int sum;
    //1为增，-1为减 
    scanline() {
        x = y1 = y2 = 0;
        sum = 0;
    }
    scanline(double x,double y1,double y2,int sum):x(x),y1(y1),y2(y2),sum(sum){}
    bool operator < (const scanline& p)const {
        return x < p.x;//按横坐标排序 
    } 
}s[maxn << 1];//2*n个扫描线，对应矩阵边界 
int size = 0;
void build(int i,int l,int r) {
    ls[i] = l;
    rs[i] = r;
    if(l == r)return ;
    int mid = l + r >> 1;
    build(i << 1 , l , mid);
    build(i << 1 | 1 , mid + 1 , r);
    return ;
}
void pushup(int i) {//因为矩阵两边界都是对应的，所以不存在cover[i]=-1的情况 
    if(cover[i]) {//如果当前整段都已被覆盖，那么直接累加上整段长度 
        len[i] = w[rs[i] + 1] - w[ls[i]];
        //因为[w[rs[i]] , w[rs[i] + 1]这一段也被覆盖，所以rs[i]+1就是把这一段也累加上 
        return ; 
    }
    else if(ls[i] == rs[i]) {
        len[i] = 0;//这里要归零！！！！！！！！！！！ 
        //叶子结点，不可能累加，直接返回
        return ; 
    }
    else {
        len[i] = len[i << 1] + len[i << 1 | 1];
        return ;
    }
    return ;
}
void update(int i,int l,int r,int val) {
    if(ls[i] > r||rs[i] < l)return ;
    if(ls[i] >= l&&rs[i] <= r) {
        cover[i] += val;
        pushup(i);//特殊点：此时要更新当前节点的len值 
        return ;
    }
    if(ls[i] == rs[i])return ;//无法递归，直接返回 
    int mid = ls[i] + rs[i] >> 1;
    if(l <= mid)update(i << 1 , l , r , val);
    if(r > mid)update(i << 1 | 1 , l , r , val);
    pushup(i);//左右节点可能有更新，所以尝试更新当前节点的len值 
    return ;
}//不得不说分治真神奇，不用考虑那么多情况 
int main() {
    freopen("atlantis.in","r",stdin);
    freopen("atlantis.out","w",stdout);
    while(~ scanf("%d",&n)) {
        if(!n)break ;
        ans = 0;
        cnt = 0;
        for(int i = 1;i <= n;++ i) {
            double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            s[++ cnt] = scanline(x1 , y1 , y2 , 1);
            w[cnt] = y1;
            s[++ cnt] = scanline(x2 , y1 , y2 , -1);
            w[cnt] = y2;
        }
        sort(s + 1 , s + 1 + cnt);
        sort(w + 1 , w + 1 + cnt);
        size = unique(w + 1 , w + 1 + cnt) - w - 1;
        build(1 , 1 , size - 1);
        for(int i = 1;i <= cnt;++ i) {
            ans += (s[i].x - s[i - 1].x) * len[1];//len[1]（根节点len值）即为所有覆盖长度
            int L = lower_bound(w + 1 , w + 1 + size , s[i].y1) - w;
            int R = lower_bound(w + 1 , w + 1 + size , s[i].y2) - w;
            update(1 , L , R - 1 , s[i].sum); 
        }           
        printf("Test case #%d\n",++ tot);
        printf("Total explored area: %.2lf\n\n",ans);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}