[JLOI2016]圆的异或并

Description

在平面直角坐标系中给定N个圆。已知这些圆两两没有交点，即两圆的关系只存在相离和包含。求这些圆的异或面积并。异或面积并为：当一片区域在奇数个圆内则计算其面积，当一片区域在偶数个圆内则不考虑。

Input

第一行包含一个正整数N，代表圆的个数。接下来N行，每行3个非负整数x,y,r，表示一个圆心在(x,y)，半径为r的圆。保证|x|,|y|,≤10^8，r>0,N<=200000

Output

仅一行一个整数，表示所有圆的异或面积并除以圆周率Pi的结果。

Sample Input

2

0 0 1

0 0 2

Sample Output

3

由于圆只存在包含与相离的关系，所以我们可以用扫描线，把圆看成一对对括号

然后判断一段区域的奇偶性，统计答案即可

至于对括号的维护，我们可以用set维护其相对位置即可

/*program from Wolfycz*/

#include<set>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define Fi first

#define Se second

#define inf 0x7f7f7f7f

#define sqr(x) ((x)*(x))

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned int ui;

typedef unsigned long long ull;

inline char gc(){

	static char buf[1000000],*p1=buf,*p2=buf;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;

}

inline int frd(){

	int x=0,f=1; char ch=gc();

	for (;ch<'0'||ch>'9';ch=gc())	if (ch=='-')	f=-1;

	for (;ch>='0'&&ch<='9';ch=gc())	x=(x<<3)+(x<<1)+ch-'0';

	return x*f;

}

inline int read(){

	int x=0,f=1; char ch=getchar();

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

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<3)+(x<<1)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x<0)	putchar('-'),x=-x;

	if (x>9)	print(x/10);

	putchar(x%10+'0');

}

const int N=2e5;

const double eps=1e-8;

double A[N+10],B[N+10],R[N+10],Nx;

struct node{

	int type,ID;

	node(int _type=0,int _ID=0){type=_type,ID=_ID;}

	void insert(int _type,int _ID){type=_type,ID=_ID;}

	double T(){return B[ID]+(double)type*(sqrt(sqr(R[ID])-sqr(Nx-A[ID]))+eps);}

};

bool operator <(node a,node b){return a.T()-b.T()<-eps;}

struct S1{

	int type,v,ID;

	void insert(int _type,int _v,int _ID){type=_type,v=_v,ID=_ID;}

	bool operator <(const S1 &tis)const{return v<tis.v;}

}opr[(N<<1)+10];//operator

bool can[N+10];

set<node>ST;

int main(){

	int n=read(),cnt=0; ll Ans=0;

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

		scanf("%lf%lf%lf",A+i,B+i,R+i);

		opr[++cnt].insert( 1,A[i]-R[i],i);

		opr[++cnt].insert(-1,A[i]+R[i],i);

	}

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

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

		Nx=opr[i].v;

		if (opr[i].type>0){

			set<node>::iterator it=ST.insert(node(1,opr[i].ID)).Fi;

			if (it==ST.begin())	can[opr[i].ID]=1;

			else{

				it--;

				can[opr[i].ID]=can[(*it).ID]^((*it).type<0);

			}

			Ans+=(can[opr[i].ID]?1:-1)*sqr(R[opr[i].ID]);

			ST.insert(node(-1,opr[i].ID));

		}else{

			ST.erase(node( 1,opr[i].ID));

			ST.erase(node(-1,opr[i].ID));

		}

	}

	printf("%lld\n",Ans);

	return 0;

}

巴特西

[JLOI2016]圆的异或并

最新文章

热门文章