AC代码

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 10000 + 10;

int n,len;
double lsh[N << 1];

struct T
{
    int l, r, cnt;
    double len;
}t[N << 4];

struct A
{
    double x, y1, y2;
    int add;
} a[N << 1];

inline bool cmp(const A &u, const A &v)
{
    return u.x < v.x;
}

inline int val(register double x)
{
    return lower_bound(lsh + 1, lsh + 1 + len, x) - lsh;
}

inline double raw(register int x)
{
    return lsh[x];
}

inline void pushup(register int u)
{
    t[u].len = (t[u].cnt > 0) ? raw(t[u].r + 1) - raw(t[u].l) : t[u << 1].len + t[u << 1 | 1].len;
}

inline void build(register int u, register int l, register int r)
{
    t[u] = {l, r, 0, 0};

    if (l == r)
        return;

    register int mid = l + r >> 1;

    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

inline void modify(register int u, register int l, register int r, register int add)
{
    if (t[u].l >= l && t[u].r <= r) 
    {
        t[u].cnt += add;
        pushup(u); 
        return;
    }

    register int mid = t[u].l + t[u].r >> 1;
    if (l <= mid) 
        modify(u << 1, l, r, add);
    if (r > mid) 
        modify(u << 1 | 1, l, r, add);

    pushup(u);
}

int main()
{
    register int id = 0;
    while ( ++ id)
    {
        scanf("%d", &n);

        if (!n) 
            break;

        printf("Test case #%d\n", id);

        for (register int i = 1; i <= n; i ++ )
        {
            register double x1, y1, x2, y2;
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            a[i] = {x1, y1, y2, 1}, a[i + n] = {x2, y1, y2, -1};
            lsh[i] = y1, lsh[i + n] = y2;
        }

        n <<= 1;

        sort(a + 1, a + 1 + n, cmp), sort(lsh + 1, lsh + 1 + n);
        len = unique(lsh + 1, lsh + 1 + n) - lsh - 1;

        build(1, 1, len - 1);

        register double ans = 0;

        modify(1, val(a[1].y1), val(a[1].y2) - 1, a[1].add);

        for (register int i = 2; i <= n; i ++ )
        {
            ans += t[1].len * (a[i].x - a[i - 1].x);
            modify(1, val(a[i].y1), val(a[i].y2) - 1, a[i].add);
        }

        printf("Total explored area: %.2lf\n\n",ans);
    }

    return 0;
}