考虑任何一条垂直于x轴的直线，由于圆不交，所以这条直线上的圆弧构成形似括号序列的样子，且直线移动时圆之间的相对位置不变。
将每个圆拆成两边，左端加右端删。每次加圆时考虑它外面最内层的括号属于谁。用set维护括号序列，每次从插入的位置往上找，如果第一个找到的是上括弧则说明被它包含，如果是下括弧说明和它并列。这样每个圆的符号就可以确定了。
1 #include2 #include 3 #include 4 #include 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 6 typedef long long ll; 7 using namespace std; 8 9 const int N=400010;10 int n,tmp,f[N];11 ll ans,x[N],y[N],r[N];12 13 struct P{ int x,f,id; }q[N];14 double gety(int id,int p,int k)15 { return y[id]+k*sqrt(r[id]*r[id]-(x[id]-p)*(x[id]-p)); }16 17 struct D{ int id,k; };18 bool operator <(const D &a,const D &b){19 return (a.id==b.id) ? a.k S;23 bool cmp(const P &a,const P &b){ return a.x==b.x ? a.f ::iterator it=S.lower_bound((D){q[i].id,1});38 if (it!=S.end()) f[q[i].id]=((it->k==1)?-1:1)*f[it->id];39 else f[q[i].id]=1;40 S.insert((D){q[i].id,1}); S.insert((D){q[i].id,-1});41 }42 }43 rep(i,1,n) ans+=f[i]*r[i]*r[i];44 printf("%lld\n",ans);45 return 0;46 }