4561: [JLoi2016]圆的异或并
Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 171 Solved: 70
[Submit][Status][Discuss]
Description
在平面直角坐标系中给定N个圆。已知这些圆两两没有交点，即两圆的关系只存在相离和包括。求这些圆的异或面
积并。异或面积并为：当1片区域在奇数个圆内则计算其面积，当1片区域在偶数个圆内则不斟酌。
Input
第1行包括1个正整数N，代表圆的个数。接下来N行，每行3个非负整数x,y,r，表示1个圆心在(x,y)，半径为r的
圆。保证|x|,|y|,≤10^8，r>0,N<=200000
Output
仅1行1个整数，表示所有圆的异或面积并除以圆周率Pi的结果。
Sample Input
2
0 0 1
0 0 2
Sample Output
3
扫描线算法
圆之间的包括关系构成1个树形结构，这棵树上奇数层圆的面积和减去偶数层圆的面积和即为答案。
求圆之间的包括关系是1个很经典的扫描线模型，详见我的hdu5299题解。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define N 200005
using namespace std;
int n,tmp,cnt,head[N],d[N],fa[N];
ll ans;
struct edge{int next,to;}e[N];
struct cir{ll x,y,r;}a[N];
struct data{int x,f,id;}q[N*2];
inline double gety(int id,int x,int opt)
{
return a[id].y+opt*sqrt(a[id].r*a[id].r-(a[id].x-x)*(a[id].x-x));
}
struct pos
{
int id,opt;
pos(int a=0,int b=0){id=a;opt=b;}
friend bool operator <(pos a,pos b)
{
if (a.id==b.id) return a.opt<b.opt;
else return gety(a.id,tmp,a.opt)<gety(b.id,tmp,b.opt);
}
};
set<pos> s;
set<pos>::iterator it;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=⑴;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline bool cmp(data a,data b){return a.x==b.x?a.f<b.f:a.x<b.x;}
inline void add_edge(int x,int y)
{
e[++cnt]=(edge){head[x],y};head[x]=cnt;
fa[y]=x;
}
void dfs(int x)
{
ll area=a[x].r*a[x].r;
if (d[x]&1) ans+=area;else ans-=area;
for(int i=head[x];i;i=e[i].next) d[e[i].to]=d[x]+1,dfs(e[i].to);
}
int main()
{
n=read();
F(i,1,n)
{
a[i].x=read();a[i].y=read();a[i].r=read();
q[2*i⑴]=(data){a[i].x-a[i].r,1,i};
q[2*i]=(data){a[i].x+a[i].r,⑴,i};
}
sort(q+1,q+2*n+1,cmp);
F(i,1,2*n)
{
if (q[i].f==1)
{
tmp=q[i].x;
it=s.lower_bound(pos(q[i].id,1));
if (it!=s.end())
{
if (it->opt==1) add_edge(it->id,q[i].id);
else add_edge(fa[it->id],q[i].id);
}
else add_edge(0,q[i].id);
s.insert(pos(q[i].id,1));s.insert(pos(q[i].id,⑴));
}
else s.erase(pos(q[i].id,1)),s.erase(pos(q[i].id,⑴));
}
dfs(0);
printf("%lld\n",ans);
return 0;
}