bzoj4561【JLOI2016】圓的異或并
來源：程序員人生 發(fā)布時(shí)間：2016-08-22 09:24:04 閱讀次數(shù)：2496次
4561: [JLoi2016]圓的異或并
Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 171 Solved: 70
[Submit][Status][Discuss]
Description
在平面直角坐標(biāo)系中給定N個(gè)圓。已知這些圓兩兩沒有交點(diǎn)，即兩圓的關(guān)系只存在相離和包括。求這些圓的異或面
積并。異或面積并為：當(dāng)1片區(qū)域在奇數(shù)個(gè)圓內(nèi)則計(jì)算其面積，當(dāng)1片區(qū)域在偶數(shù)個(gè)圓內(nèi)則不斟酌。
Input
第1行包括1個(gè)正整數(shù)N，代表圓的個(gè)數(shù)。接下來N行，每行3個(gè)非負(fù)整數(shù)x,y,r，表示1個(gè)圓心在(x,y)，半徑為r的
圓。保證|x|,|y|,≤10^8，r>0,N<=200000
Output
僅1行1個(gè)整數(shù)，表示所有圓的異或面積并除以圓周率Pi的結(jié)果。
Sample Input
2
0 0 1
0 0 2
Sample Output
3
掃描線算法
圓之間的包括關(guān)系構(gòu)成1個(gè)樹形結(jié)構(gòu)，這棵樹上奇數(shù)層圓的面積和減去偶數(shù)層圓的面積和即為答案。
求圓之間的包括關(guān)系是1個(gè)很經(jīng)典的掃描線模型，詳見我的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;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
