[spoj CIRU2]关于圆面积并的思考，非simpson！！

2019-11-10 19:05:21

字体：大中小

来源：转载

供稿：网友

aekdycoin神犇的讲解图一是普通求圆并的思路，复杂度O（n^2 logn）图二是神犇给的提示，没有题解…

一开始困扰了好久，我觉得这和hzwer开的坏头有关，他在BZOJ上圆并用了simpson之后一大批同学思路都跟着“奇怪”了起来，这题simpson没试过，不过评论说会挂精度。首先我们要理解非simpson的圆并在干什么？这个算法很神的地方在于他把圆并分成了好多个圆弧和一个多边形，然后分别求面积，圆弧部分是一个圆上未被其它圆覆盖的部分的圆弧（可能有多段），而多边形则被分解为每条边单独算贡献。这样我们的工作就简单许多了，枚举一个圆，与其它圆求交点，搞出区间后排序，统计未覆盖的角度算圆弧，统计坐标算叉积求贡献。最后统统加起来就好了。注意一些被包含的圆没有作用，标记掉即可！现在再看那张提示图，我们发现一个圆未被其它圆覆盖的部分就是圆并的“一次覆盖面积”（见spoj ciru2），我们大胆的猜一个结论：“k次覆盖面积”就是k次覆盖的圆弧加多边形面积。呵呵...结果就是这样... 注意这时被包含的圆不是去掉，是统计时覆盖次数加一！废话就这么多，总之细节很烦，对拍造数据要考虑数据的合法性...

普通圆并

#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef long long LL;inline int read() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f;}const int MAXN=1003;const double PI=3.141592653589793238462,eps=1e-8;int n,m;double ans1,ans2,b[MAXN],R[MAXN];struct P{ double x,y; P(double v=0,double u=0){ x=v; y=u; } double len(){ return sqrt(x*x+y*y); } P Operator +(const P &E)const{ return P(x+E.x,y+E.y); } P operator -(const P &E)const{ return P(x-E.x,y-E.y); } P operator *(const double &z)const{ return P(x*z,y*z); } P operator /(const double &z)const{ return P(x/z,y/z); } double operator *(const P &E)const{ return x*E.x+y*E.y; }}a[MAXN];inline double cross(P p,P q){ return p.x*q.y-p.y*q.x; }inline double dist(P p,P q){ return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)); }struct Data{ P ax,ay; double x,y; bool operator <(const Data &E)const{ return (x<E.x)||((x==E.x)&&(y<E.y)); }}c[MAXN*2];inline P rot(P p,double a){ return P(cos(a)*p.x-sin(a)*p.y,sin(a)*p.x+cos(a)*p.y); }inline double deg(P p){ double tmp=atan2(p.y,p.x); return tmp<0?tmp+PI*2:tmp;}inline void work(P o1,P o2,double r1,double r2){ double s,p,h,alpha,tmp=dist(o1,o2); p=(r1+r2+tmp)/2; s=sqrt(p*(p-r1)*(p-r2)*(p-tmp)); h=s*2/tmp; alpha=asin(h/r1); if (r1*r1+tmp*tmp<r2*r2) alpha=PI-alpha; m++; c[m].ax=rot(o2-o1,PI*2-alpha)/tmp*r1+o1; c[m].ay=rot(o2-o1,alpha)/tmp*r1+o1; c[m].x=deg(c[m].ax-o1); c[m].y=deg(c[m].ay-o1); if (c[m].x>c[m].y) { m++; c[m].y=c[m-1].y; c[m].ay=c[m-1].ay; c[m-1].y=PI*2; c[m].x=0; c[m-1].ay=c[m].ax=o1+P(r1,0); }}int main() { //freopen("1.in","r",stdin); //freopen("2.out","w",stdout); int i,j,k,l; m=read(); for (i=1,n=0;i<=m;++i) { n++; a[n].x=read(); a[n].y=read(); R[n]=read(); if (fabs(R[n])<=eps) n--; } memset(b,0,sizeof(b)); for (i=1;i<=n;++i) if (!b[i]) for (j=1;j<=n;++j) if (!b[j]&&i!=j&&dist(a[i],a[j])<=R[j]-R[i]) { b[i]=1; break; } //for (i=1;i<=n;++i) if (!b[i]) PRintf("%d/n",i); for (i=1,ans1=ans2=0;i<=n;++i) if (!b[i]) { for (j=1,m=0;j<=n;++j) if (!b[j]&&i!=j&&dist(a[i],a[j])<R[i]+R[j]) work(a[i],a[j],R[i],R[j]); if (m==0) { ans2+=PI*R[i]*R[i]; continue; } sort(c+1,c+1+m); c[0].y=0; c[m+1].x=PI*2; c[0].ay=c[m+1].ax=a[i]+P(R[i],0); /*for (j=1;j<=m;++j) { printf("%.8lf %.8lf/n",c[j].x,c[j].y); printf("%.8lf %.8lf||%.8lf %.8lf/n",c[j].ax.x,c[j].ax.y,c[j].ay.x,c[j].ay.y); }*/ double tmp=0; for (j=0;j<=m;j=k+1) { for (k=l=j;k<m&&c[k+1].x<=c[l].y;++k) if (c[k+1].y>c[l].y) l=k+1; ans1+=cross(c[l].ay,c[k+1].ax); tmp=c[k+1].x-c[l].y; ans2+=R[i]*R[i]*(tmp-sin(tmp))/2; } //printf("%d %d %.8lf %.8lf/n",i,m,ans1,ans2); } printf("%.5lf/n",fabs(ans1)/2+ans2); //fclose(stdin); //fclose(stdout); return 0;}/*24 2 53 3 4*/

spoj ciru2

#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef long long LL;inline int read() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f;}const int MAXN=1003;const double PI=3.1415926535897932384626433832795028841971693993,eps=1e-8;int n,m;double ans[MAXN][2],b[MAXN],R[MAXN];struct P{ double x,y; P(double v=0,double u=0){ x=v; y=u; } double len(){ return sqrt(x*x+y*y); } P operator +(const P &E)const{ return P(x+E.x,y+E.y); } P operator -(const P &E)const{ return P(x-E.x,y-E.y); } P operator *(const double &z)const{ return P(x*z,y*z); } P operator /(const double &z)const{ return P(x/z,y/z); } double operator *(const P &E)const{ return x*E.x+y*E.y; }}a[MAXN];inline double cross(P p,P q){ return p.x*q.y-p.y*q.x; }inline double dist(P p,P q){ return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)); }struct Data{ P ax; double x; int y; bool operator <(const Data &E)const{ return x<E.x; }}c[MAXN*10];inline P rot(P p,double a){ return P(cos(a)*p.x-sin(a)*p.y,sin(a)*p.x+cos(a)*p.y); }inline double deg(P p){ double tmp=atan2(p.y,p.x); return tmp<0?tmp+PI*2:tmp;}inline void work(P o1,P o2,double r1,double r2){ double s,p,h,alpha,tmp=dist(o1,o2); p=(r1+r2+tmp)/2; s=sqrt(p*(p-r1)*(p-r2)*(p-tmp)); h=s*2/tmp; alpha=asin(h/r1); if (r1*r1+tmp*tmp<r2*r2) alpha=PI-alpha; c[++m].ax=rot(o2-o1,PI*2-alpha)/tmp*r1+o1; c[m].x=deg(c[m].ax-o1); c[m].y=1; c[++m].ax=rot(o2-o1,alpha)/tmp*r1+o1; c[m].x=deg(c[m].ax-o1); c[m].y=-1; if (c[m-1].x>c[m].x) { c[++m].ax=o1+P(r1,0); c[m].x=0; c[m].y=1; c[++m].ax=o1+P(r1,0); c[m].x=PI*2; c[m].y=-1; }}int main() { //freopen("1.in","r",stdin); //freopen("2.out","w",stdout); int i,j,k,l; n=read(); for (i=1;i<=n;++i) { a[i].x=read(); a[i].y=read(); R[i]=read(); } memset(b,0,sizeof(b)); for (i=1;i<=n;++i) for (j=1;j<=n;++j) if (i!=j&&dist(a[i],a[j])<=R[j]-R[i]) b[i]++; memset(ans,0,sizeof(ans)); for (i=1;i<=n;++i) { for (j=1,m=0;j<=n;++j) if (i!=j&&dist(a[i],a[j])<R[i]+R[j]&&dist(a[i],a[j])>fabs(R[j]-R[i])) work(a[i],a[j],R[i],R[j]); c[++m].ax=a[i]+P(R[i],0); c[m].x=0; c[m].y=b[i]+1; c[++m].ax=a[i]+P(R[i],0); c[m].x=PI*2; c[m].y=-b[i]-1; sort(c+1,c+1+m); /*printf("%d/n",i); for (j=1;j<=m;++j) { printf("%d %.3lf %d/n",j,c[j].x,c[j].y); printf("(%.3lf,%.3lf)/n",c[j].ax.x,c[j].ax.y); }*/ int sa=1,sb=0,sc; for (j=1;j<=m;j=k+1) { for (k=j;k<m&&fabs(c[k+1].x-c[j].x)<eps;++k); for (l=j,sc=sb;l<=k;++l) sc+=c[l].y; if (sc==sb&&k!=m) continue; if (fabs(c[sa].x-c[j].x)>eps) { ans[sb][0]+=cross(c[sa].ax,c[j].ax); double tmp=c[j].x-c[sa].x; ans[sb][1]+=R[i]*R[i]*(tmp-sin(tmp))/2; } sb=sc; sa=j; } } //for (i=1;i<=n;++i) printf("%.3lf %.3lf %.3lf/n",ans[i][0],ans[i][1],fabs(ans[i][0])/2+ans[i][1]); for (i=1;i<=n;++i) ans[i][0]=fabs(ans[i][0])/2+ans[i][1]; for (i=1;i<=n;++i) printf("[%d] = %.3lf/n",i,ans[i][0]-ans[i+1][0]); //fclose(stdin); //fclose(stdout); return 0;}/*53 0 34 3 51 2 44 3 51 4 4*/ 身为一个蒟蒻非常同情蒟蒻写完程序死WA不止，希望我的程序对蒟蒻们的学习(对拍)有帮助。

上一篇：[模版] K/最近邻匹配（KD Tree）

下一篇：Codeforces Round #362 (Div. 2)B. Barnicle（较坑模拟【菜鸡与大佬的区别】）