看题解看了半天......
Code:
#include<bits/stdc++.h>
#define maxn 200010
#define ll long long
using namespace std;
void setIO(string s)
{
string in=s+".in";
freopen(in.c_str(),"r",stdin);
}
struct cir
{
ll x,y,r;
}c[maxn];
struct use
{
int p,x,k;
}q[maxn<<1];
set<use>S;
set<use>::iterator it;
int n;
ll temp,g[maxn],ans;
ll calc(ll x) { return x * x; }
bool cmp(use a,use b)
{
return a.x < b.x;
}
bool operator<(use a,use b)
{
double x = c[a.p].y + a.k * sqrt(calc(c[a.p].r) - calc(temp - c[a.p].x));
double y = c[b.p].y + b.k * sqrt(calc(c[b.p].r) - calc(temp - c[b.p].x));
return x==y ? a.k<b.k : x < y;
}
int main()
{
// setIO("input");
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%lld%lld%lld",&c[i].x,&c[i].y,&c[i].r);
q[(i<<1)-1]=use{i,c[i].x-c[i].r,1}; // 上圆弧
q[i<<1]={i,c[i].x+c[i].r,-1}; // 下圆弧
}
sort(q+1,q+(n<<1)+1,cmp); // 按照横坐标排序
for(int i=1;i<=(n<<1);++i)
{
temp=q[i].x;
if(q[i].k==1)
{
it=S.upper_bound(use{q[i].p,0,-1});
if(it==S.end()) g[q[i].p]=1;
else
{
if((*it).k==-1) g[q[i].p]=g[(*it).p];
else
{
g[q[i].p]=-g[(*it).p];
}
}
S.insert(use{q[i].p,0,1});
S.insert(use{q[i].p,0,-1});
}
else
{
S.erase(use{q[i].p,0,1});
S.erase(use{q[i].p,0,-1});
}
}
for(int i=1;i<=n;++i)
{
ans += calc(c[i].r) * g[i];
}
printf("%lld\n",ans);
return 0;
}