題目鏈接多校8-1009 HDU - 6158 The Designer

題意

T（<=1200）組，如圖在半徑R1、R2相內切的圓的差集位置依次繪制1,2,3,到n號圓，求面積之和（n<=1e7)。

題解

圓的反演：
（圓的反演就是半徑為R，圓心O的圓為反演中心，點P的反演點就是在射線OP上滿足\(|OP’|*|OP|=R^2\)的點P‘）
設切點為O，以O為圓心半徑R的圓為反演點。將圓R1和R2反演得到兩條直線，和兩條直線相切的圓反演回去的圓就是1～n號圓的圓心。
那么它們的直徑就是這些小圓的圓心和O的連線與小圓的交點反演回去的點的距離差。

再扔一次畫圖工具Desmos

比賽的時候想到這里就以為復雜度太高，不知道怎么預處理。其實到后面圓面積會收斂得很快。精度只要1e-5,就可以及時break掉。

代碼

#include <bits/stdc++.h> using namespace std; const double pi = acos(-1); const double R = 1; int t,r1,r2,n; double r0,d,a,b,r,s; double ans; int main() {scanf("%d",&t);while(t--){scanf("%d%d%d",&r1,&r2,&n);if(r2<r1)swap(r1,r2);d=R*(r1+r2)/r2/r1/4;r0=d-R/2/r1;r=r2-r1;ans=pi*r*r;for(int i=1;i<=n/2;++i){a=sqrt(d*d+i*r0*i*r0*4)-r0,b=a+r0*2;r=(R/a-R/b)/2;s=pi*r*r;ans+=s;if(i*2<n)ans+=s;if(s*(n-i*2)<1e-6){break;}}printf("%.5f\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的「HDU6158」 The Designer（圆的反演）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。