国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > bzoj4561【JLOI2016】圆的异或并

bzoj4561【JLOI2016】圆的异或并

来源:程序员人生   发布时间:2016-08-22 09:24:04 阅读次数:2314次

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; }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生