Chlience

【题解】BZOJ 4561 [JLOI2016]圆的异或并
Problem给定 $n$ 个圆,求其异或面积并Thought求出每个圆被包含在哪个圆内显然这是一个树形结构,维护...
扫描右侧二维码阅读全文
29
2019/01

【题解】BZOJ 4561 [JLOI2016]圆的异或并

Problem

给定 $n$ 个圆,求其异或面积并

Thought

求出每个圆被包含在哪个圆内
显然这是一个树形结构,维护奇数层和偶数层的面积,求差即可

听起来好简单
码起来好复杂

考虑如何求出包含当前圆的圆

考虑某个圆上方任意一点,如果这个点是另一个圆的上半部分,那么这个圆被其包含
否则,这个圆和另一个圆同被一个圆包含

所以说需要维护上圆弧和下圆弧

每次扫描线扫过来碰到左端点加入圆弧,右端点删除圆弧,Splay 维护相对关系(从高到低)

具体实现每个点存下圆心位置,半径,属于上圆弧还是下圆弧,然后每次在 Splay 上比较,若 Splay 上的点在 $x=$ 当前点左端点 位置上比它高,则插入到右边,否则,插入到左边

求出每个上圆弧的前驱即可得到父子关系

当然用 set 也是可以的,并且代码非常短...
但是架不住我 Splay 快是吧

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
struct Cir {
    int x, y, r, flag, id;
};
int n;
long long w[N];
Cir U[N], D[N];
int u[N], d[N];
int ins[N], del[N];
int fa[N];
long long f[2];
struct Splay {
    int rt, tot;
    int fa[N << 1], ch[N << 1][2];
    Cir c[N << 1];
    bool get(int x) {return ch[fa[x]][1] == x;}
    void rotate(int x) {
        int old = fa[x], oldf = fa[old], w = get(x);
        ch[old][w] = ch[x][w ^ 1]; fa[ch[old][w]] = old;
        ch[x][w ^ 1] = old; fa[old] = x;
        fa[x] = oldf;
        if(oldf)
            ch[oldf][ch[oldf][1] == old] = x;
    }
    void splay(int x, int tar) {
        for(int f; (f = fa[x]) != tar; rotate(x))
            if(fa[f] != tar)
                rotate(get(x) == get(f) ? f : x);
        if(!tar)
            rt = x;
    }
    bool uper(Cir a, Cir b, int x) {
        if(a.flag == 2) return 1;
        if(a.flag == 3) return 0;
        if(a.id == b.id) return a.flag == 1;
        double ca = (1.0 * a.r * a.r - 1.0 * (x - a.x) * (x - a.x));
        return sqrt(ca) * a.flag + a.y > b.y;
    }
    int insert(Cir C, int x) {
        c[x] = C;
        if(!rt) {
            rt = x;
            return 0;
        }
        int pre = 0, now = rt;
        while(1) {
            if(uper(c[now], c[x], c[x].x - c[x].r)) {
                pre = c[now].id;
                if(c[now].flag == - 1)
                    pre = :: fa[pre];
                if(ch[now][1])
                    now = ch[now][1];
                else {
                    fa[x] = now;
                    ch[now][1] = x;
                    splay(x, 0);
                    return pre;
                }
            }
            else {
                if(ch[now][0])
                    now = ch[now][0];
                else {
                    fa[x] = now;
                    ch[now][0] = x;
                    splay(x, 0);
                    return pre;
                }
            }
        }
    }
    int pre() {
        int p = ch[rt][0];
        while(ch[p][1])
            p = ch[p][1];
        return p;
    }
    int nxt() {
        int p = ch[rt][1];
        while(ch[p][0])
            p = ch[p][0];
        return p;
    }
    void del(int x) {
        splay(x ,0);
        int l = pre();
        int r = nxt();
        splay(l ,0);
        splay(r, l);
        ch[r][0] = 0;
    }
}s;
struct Edge {
    int t, n;
};
Edge e[N];
int head[N], tot;

bool cmp1(int a, int b) {
    if(U[a].x - U[a].r == U[b].x - U[b].r)
        return U[a].y > U[b].y;
    return U[a].x - U[a].r < U[b].x - U[b].r;
}
bool cmp2(int a, int b) {
    if(U[a].x + U[a].r == U[b].x + U[b].r)
        return U[a].y > U[b].y;
    return U[a].x + U[a].r < U[b].x + U[b].r;
}
void addedge(int u, int v) {
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}
void dfs(int x, int dep) {
    for(int i = head[x]; i; i = e[i].n)
        dfs(e[i].t, dep + 1);
    f[dep % 2] += w[x];
}
int main() {
    n = read();
    Cir l = {0,0,0,2,0}, r = {0,0,0,3,0};
    s.insert(l, ++ s.tot); s.insert(r, ++ s.tot);
    for(int i = 1; i <= n; ++ i) {
        int x = read(), y = read(), r = read();
        U[i] = {x, y, r, 1, i};
        D[i] = {x, y, r, - 1, i};
        ins[i] = i; del[i] = i;
        w[i] = 1ll * r * r;
    }
    sort(ins + 1, ins + n + 1, cmp1);
    sort(del + 1, del + n + 1, cmp2);
    int lins = 1, ldel = 1;
    int pos = - 1000000000;
    while(lins <= n || ldel <= n) {
        if(lins > n) {
            s.del(u[del[ldel]]);
            s.del(d[del[ldel]]);
            ++ ldel;
        }
        else if(ldel > n) {
            u[ins[lins]] = ++ s.tot;
            fa[ins[lins]] = s.insert(U[ins[lins]], u[ins[lins]]);
            d[ins[lins]] = ++ s.tot;
            s.insert(D[ins[lins]], d[ins[lins]]);
            ++ lins;
        }
        else {
            int pos = min(U[ins[lins]].x - U[ins[lins]].r, U[del[ldel]].x + U[del[ldel]].r);
            while(lins <= n && U[ins[lins]].x - U[ins[lins]].r == pos) {
                u[ins[lins]] = ++ s.tot;
                fa[ins[lins]] = s.insert(U[ins[lins]], u[ins[lins]]);
                d[ins[lins]] = ++ s.tot;
                s.insert(D[ins[lins]], d[ins[lins]]);
                ++ lins;
            }
            while(ldel <= n && U[del[ldel]].x + U[del[ldel]].r == pos) {
                s.del(u[del[ldel]]);
                s.del(d[del[ldel]]);
                ++ ldel;
            }
        }
    }
    for(int i = 1; i <= n; ++ i)
        addedge(fa[i], i);
    dfs(0, 0);
    printf("%lld\n", f[1] - f[0]);
    return 0;
}
Last modification:January 29th, 2019 at 09:24 pm

Leave a Comment