BZOJ4561 JLOI2016圆的异或并（扫描线+平衡树）

　　考虑一条扫描线从左到右扫过这些圆。观察某一时刻直线与这些圆的交点，可以发现构成一个类似括号序列的东西，括号的包含关系与圆的包含关系是相同的。并且当扫描线逐渐移动时，括号间的相对顺序不变。于是考虑用set维护这个括号序列，插入时统计被包含层数。这只需要查询后继括号，如果是右括号则被该括号包含，答案为该括号次数+1，否则处于同一层，答案与该括号相同。

　　bzoj大概又出了一些奇怪的精度问题，用long double才过。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<set>

#include<cassert>

using namespace std;

#define ll long long

#define N 200010

#define double long double

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,cur,ans[N];

const double eps=1E-;

ll tot;

double pos(int a,int b,int r,int op){return b+op*(sqrt(1ll*r*r-1ll*(cur-a)*(cur-a))+eps);}

struct data

{

    int x,y,r,i,op;

    bool operator <(const data&a) const

    {

        return pos(x,y,r,op)<pos(a.x,a.y,a.r,a.op);

    }

}a[N<<];

multiset<data> q;

bool cmp(const data&a,const data&b)

{

    return a.x+a.op*a.r<b.x+b.op*b.r;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4561.in","r",stdin);

    freopen("bzoj4561.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].r=read(),a[i].op=-,a[i].i=i;

    for (int i=n+;i<=n+n;i++) a[i].x=a[i-n].x,a[i].y=a[i-n].y,a[i].r=a[i-n].r,a[i].op=,a[i].i=a[i-n].i;

    sort(a+,a+n+n+,cmp);

    for (int i=;i<=n+n;i++)

    {

        cur=a[i].x+a[i].op*a[i].r;

        if (a[i].op==) q.erase((data){a[i].x,a[i].y,a[i].r,a[i].i,-}),q.erase((data){a[i].x,a[i].y,a[i].r,a[i].i,});

        else

        {

            q.insert((data){a[i].x,a[i].y,a[i].r,a[i].i,-}),q.insert((data){a[i].x,a[i].y,a[i].r,a[i].i,});

            set<data>::iterator it=q.find((data){a[i].x,a[i].y,a[i].r,a[i].i,});

            it++;if (it!=q.end()) ans[a[i].i]=(*it).op==?ans[(*it).i]^:ans[(*it).i];

            if (ans[a[i].i]) tot-=1ll*a[i].r*a[i].r;else tot+=1ll*a[i].r*a[i].r;

        }

    }

    cout<<tot;

    return ;

}