bzoj 4561: [JLoi2016]圆的异或并

Description

在平面直角坐标系中给定N个圆。已知这些圆两两没有交点，即两圆的关系只存在相离和包含。求这些圆的异或面

积并。异或面积并为：当一片区域在奇数个圆内则计算其面积，当一片区域在偶数个圆内则不考虑。

Solution

我们可以把异或当作容斥的一个过程....现在要确定每一个圆的系数.

由于不存在相交关系 , 圆与圆之间相对顺序是确定的 , 所以可以用 \(set\) 来维护相对顺序.

我们对 \(x\) 做扫描线来维护一个圆的插入和删除.

我们把一个圆拆成上下两个圆弧 , 新插入一个圆时 , 判断上面的第一个圆弧是上圆弧还是下圆弧.

容易发现 : 如果是上圆弧那么系数相反 , 如果是下圆弧则相同.

求出每个圆的系数 , 最后累加答案就行了.

注意一个细节 , 上下圆弧 \(y\) 相同时 , 要把下圆弧放在下面...

#include<bits/stdc++.h>

#define sqr(x) (1ll*(x)*(x))

using namespace std;

template<class T>void gi(T &x){

	int f;char c;

	for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;

	for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;

}

const int N=200010;

int n,f[N],y[N],r[N],X,x[N];

struct data{int id,k;}q[N*2];

inline bool operator <(data p,data q){

	return x[p.id]+r[p.id]*p.k<x[q.id]+r[q.id]*q.k;

}

struct node{int id,k;};

inline bool operator <(node p,node q){

	double y1=y[p.id]+p.k*sqrt(sqr(r[p.id])-sqr(X-x[p.id]));

	double y2=y[q.id]+q.k*sqrt(sqr(r[q.id])-sqr(X-x[q.id]));

	if(y1<y2)return 1;if(y1>y2)return 0;

	return p.k<q.k;

}

set<node>S;

set<node>::iterator it;

int main(){

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

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

  cin>>n;

  int cnt=0;

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

	  gi(x[i]),gi(y[i]),gi(r[i]);

	  q[++cnt]=(data){i,-1},q[++cnt]=(data){i,1};

  }

  sort(q+1,q+cnt+1);

  for(int i=1;i<=cnt;i++){

	  X=x[q[i].id]+q[i].k*r[q[i].id];

	  if(q[i].k==-1){

		  int x=q[i].id;

		  node t1=(node){x,1},t2=(node){x,-1};

		  it=S.lower_bound(t1);

		  if(it!=S.end()){

			  if(it->k>0)f[x]=-f[it->id];

			  else f[x]=f[it->id];

		  }

		  else f[x]=1;

		  S.insert(t1),S.insert(t2);

	  }

	  else S.erase((node){q[i].id,1}),S.erase((node){q[i].id,-1});

  }

  long long ans=0;

  for(int i=1;i<=n;i++)ans+=1ll*f[i]*r[i]*r[i];

  cout<<ans;

  return 0;

}