考虑一条扫描线从左到右扫过这些圆。观察某一时刻直线与这些圆的交点,可以发现构成一个类似括号序列的东西,括号的包含关系与圆的包含关系是相同的。并且当扫描线逐渐移动时,括号间的相对顺序不变。于是考虑用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 ;
}
05-11 22:50