【题解】[JLoi2016] 圆的异或并 扫描线 BZOJ – 4561

题目链接=￣ω￣=

把每个圆按照左端点横坐标排序

扫描线从左往右（线是垂直于 $x$轴的）扫过去

因为圆不相交也不想切，所以在扫描线移动过程中，扫描线与那些圆的交点的相对排序关系是不会改变的

每遇到一个圆的左端点就把它的上半圆和下半圆加进去，遇到右端点就减掉

还有在扫到左端点的时候要查询该点的上方第一个弧是下半圆还是上半圆，如果是上半圆说明当前圆包含在那个半圆所代表的圆中（即父子关系），是下半圆则说明它们包含在同一个圆中（即兄弟关系），这样就能够成一棵树

弧的排序关系用与当前扫描线的交点的纵坐标表示就行了，因为前面说过的，移动扫描线对于已经扫过的弧的相对关系是没有影响的

用 set 维护这些弧就行了

最后对于这棵树，每个树上结点都代表一个圆，如果这个点的深度为奇数，则它对答案的贡献就是正的它的面积，如果深度为偶数贡献就是负的它的面积

复杂度 $O(n log _ 2 n)$

代码：

#include <bits/stdc++.h>

#define NS (400005)

using namespace std;

typedef pair<int, int> PII;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct circle
{
    int x, y, r, u, d;
} P[NS];

int X;

double F(int a, int t)
{
    int x = X - P[a].x;
    if (!t) t = -1;
    return sqrt((double)P[a].r * P[a].r - (double)x * x) * t + P[a].y;
}

struct half
{
    int c, t;
    bool operator < (const half oth) const
    {
        double f1 = F(c, t), f2 = F(oth.c, oth.t);
        if (fabs(f1 - f2) < 1e-10) return t < oth.t;
        return f1 < f2;
    }
} Q[NS];

int n, qc, ec, fa[NS], f[NS];

set<half> st;

typedef set<half>::iterator itr;

PII event[NS];

long long ans;

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 1; i <= n; i += 1)
    {
        IN(P[i].x), IN(P[i].y), IN(P[i].r);
        Q[++qc].c = i, Q[qc].t = 1, P[i].u = qc;
        Q[++qc].c = i, Q[qc].t = 0, P[i].d = qc;
        event[++ec] = PII(P[i].x - P[i].r, i);
        event[++ec] = PII(P[i].x + P[i].r, -i);
    }
    sort(event + 1, event + 1 + ec), f[0] = -1;
    for (int i = 1; i <= ec; i += 1)
    {
        int a = event[i].second;
        if (a < 0)
        {
            X = P[-a].x + P[-a].r;
            st.erase(Q[P[-a].u]), st.erase(Q[P[-a].d]);
            continue;
        }
        X = P[a].x - P[a].r;
        itr it = st.insert(Q[P[a].u]).first, tmp = it;
        if (++tmp != st.end())
        {
            if (tmp->t) fa[a] = tmp->c;
            else fa[a] = fa[tmp->c];
        }
        else fa[a] = 0;
        st.insert(Q[P[a].d]), f[a] = -f[fa[a]];
        ans += 1ll * P[a].r * P[a].r * f[a];
    }
    printf("%lld\n", ans);
    return 0;
}