记录编号	582273	评测结果	AAAAAAAAAA
题目名称	[POJ 1151]亚特兰蒂斯	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.812 s
提交时间	2023-09-07 17:25:08	内存使用	39.31 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
int n,u;
double ans;
struct T{
    int l,r,sum;
    double len;
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define sum(x) t[x].sum
    #define len(x) t[x].len
}t[4*N];
struct made{
    int ed;
    double x,y1,y2;
    made(){}
    made(double x,double y1,double y2,int ed):x(x),y1(y1),y2(y2),ed(ed){} 
    bool operator < (const made& p)const{
        return x < p.x;
    }
}line[2*N];
double shu[2*N];
int cnt;
void build(int x,int l,int r){
    l(x) = l,r(x) = r;
    if(l == r)return;
    int mid = (l + r) >> 1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
}
void pushup(int x){
    if(sum(x) > 0)len(x) = shu[r(x)+1] - shu[l(x)];
    else if(l(x) == r(x))len(x) = 0;
    else len(x) = len(x<<1) + len(x<<1|1);
}
void add(int x,int l,int r,int ed){
    if(l <= l(x) && r(x) <= r){
        sum(x) += ed;
        pushup(x);
        return;
    }
    int mid = (l(x) + r(x)) >> 1;
    if(mid >= l)add(x<<1,l,r,ed);
    if(mid < r)add(x<<1|1,l,r,ed);
    pushup(x);
}
int main(){
    freopen("atlantis.in","r",stdin);
    freopen("atlantis.out","w",stdout);
    while(scanf("%d",&n) && n){
        u++;ans = 0,cnt = 0;
        memset(shu,0,sizeof(shu));
        memset(line,0,sizeof(line));
        memset(t,0,sizeof(t));
        for(int i = 1;i <= n;i++){
            double a,b,c,d;
            scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
            cnt++;
            shu[cnt] = b,line[cnt] = made(a,b,d,1);
            cnt++;
            shu[cnt] = d,line[cnt] = made(c,b,d,-1);
        }
        sort(shu+1,shu+1+cnt);
        sort(line+1,line+1+cnt);
        int m = unique(shu+1,shu+cnt+1) - (shu+1);
        build(1,1,m-1);
        for(int i = 1;i < cnt;i++){
            int l = lower_bound(shu+1,shu+1+m,line[i].y1) - shu;
            int r = lower_bound(shu+1,shu+1+m,line[i].y2) - shu;
            add(1,l,r-1,line[i].ed);
            ans = ans + t[1].len * (line[i+1].x - line[i].x);
        }
        printf("Test case #%d\n",u);
        printf("Total explored area: %.2lf\n\n",ans);
    }
    
    return 0;
    
}