bzoj 4561: [JLoi2016]圆的异或并

题意：

平面上有$n$个圆，之间的关系只有相离或包含。求被奇数个圆覆盖的面积。

题解：

学习了如何用扫描线和set求圆的包含关系。
扫描线从左往右扫。set中维护扫描线穿过的半圆（把圆拆成上半圆和下半圆），关键字为交点的纵坐标（虽然随着扫描线的移动这个值是会变的，但相对顺序不会变）。遇到一个新圆（左端点）时，在set中找到最大的比新圆的圆心（左端点）的纵坐标小的半圆，如果是个上半圆，则表示这包含这两个圆的是同一个圆；如果是下半圆，则表示这个圆包含了新圆。离开一个圆（右端点）时，从set里删除它的两个半圆即可。

代码：

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-9;
int n, nowx, num = 0, dep[200010];
long long ans = 0;
struct th
{
    int x, y, r, id, type;
} a[400010];
struct thh
{
    int x, y, r, type, id;
    thh(int x, int y, int r, int type, int id) : x(x), y(y), r(r), type(type), id(id) {}
    double get() const
    {
        return y + type * sqrt(1LL * r * r - 1LL * (x - nowx) * (x - nowx));
    }
};
bool operator<(thh x, thh y)
{
    if (abs(x.get() - y.get()) < eps)
    {
        return x.type == y.type ? (x.type == 1 ? x.r < y.r : x.r > y.r) : x.type < y.type;
    }
    else return x.get() < y.get();
}
set<thh> s;
set<thh>::iterator it1[200010], it2[200010];

int cmp(th x, th y)
{
    return x.x == y.x ?
    (
        x.type == y.type ?
            x.r > y.r
        :
            x.type < y.type
    )
    :
        x.x < y.x;
}
int main()
{
    // freopen("4561.in", "r", stdin);
    // freopen("4561.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int x, y, r;
        scanf("%d%d%d", &x, &y, &r);
        a[++num] = {x - r, y, r, i, 1};
        a[++num] = {x + r, y, r, i, -1};
    }
    sort(a + 1, a + 1 + num, cmp);
    for (int i = 1; i <= num; i++)
    {
        // printf("%d %d %d %d %d\n", a[i].x, a[i].y, a[i].r, a[i].type, a[i].id);
        nowx = a[i].x;
        if (a[i].type == 1)
        {
            set<thh>::iterator it = s.lower_bound(thh(a[i].x + a[i].r, a[i].y, a[i].r, 1, 0));
            if (it == s.begin()) dep[a[i].id] = 0;
            else
            {
                it--;
                // printf("%d %d\n", it->id, it->type);
                if (it->type == 1) dep[a[i].id] = dep[it->id];
                else dep[a[i].id] = dep[it->id] + 1;
            }
            it1[a[i].id] = s.insert(thh(a[i].x + a[i].r, a[i].y, a[i].r, 1, a[i].id)).first;
            it2[a[i].id] = s.insert(thh(a[i].x + a[i].r, a[i].y, a[i].r, -1, a[i].id)).first;
            if (dep[a[i].id] & 1) ans -= 1LL * a[i].r * a[i].r;
            else ans += 1LL * a[i].r * a[i].r;
        }
        else
        {
            s.erase(it1[a[i].id]);
            s.erase(it2[a[i].id]);
        }
    }/*
    for (int i = 1; i <= n; i++)
        printf("%d ", dep[i]);
    puts("");*/
    printf("%lld\n", ans);
}