[spoj CIRU2]關于圓面積并的思考，非simpson??！

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.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不止，希望我的程序對蒟蒻們的學習(對拍)有幫助。

[spoj CIRU2]關于圓面積并的思考，非simpson??！

[spoj CIRU2]關于圓面積并的思考，非simpson??！