hdu6158

201708 （ACM）计算几何----圆反演

题意

• 求前n个小圆面积。
  

笛卡尔定理

• 定义一个圆的曲率 $k=±(1/r)$ ，其中 $r$ 是其半径。
• 若平面有两两相切，且有6个独立切点的四个圆，设其曲率为 $k_1,k_2,k_3,k_4$ 则其满足性质：
  
  • 若四圆两两外切，则$(k_1+k_2+k_3+k_4)^2=2*(k_1^2+k_2^2+k_3^2+k_4^2)$
  • 若半径为$r_1$、$r_2$、$r_3$的圆内切于半径为$r_4$的圆中，则$(k_1+k_2+k_3+k_4)^2=2*(k_1^2+k_2^2+k_3^2+k_4^2)$ $(k_4=-(1/r))$

韦达定理

• $x_1+x_2=−(b/a)$
• $x_1×x_2=c/a$

题解

• 对于此题，第一个与已知圆相切的圆的半径非常好求，其半径$r_3=(r_1−r_2)$，其中$r_1$是已知圆中较大圆的半径。
• 故我们现在$k_1,k_2,k_3$均为已知，代入上面笛卡尔定理的式子便能求解出$k_4$。
• 易发现这是一个关于$k_4$的二次方程，化简为标准形式，设两个解是$x_1,x_2$，利用韦达定理化简：$x_1+x_2=2*(-k_1+k_2+k_3)$
• 然后接着递推即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef double db;
const db eps=1e-13;
const db pi=acos(-1);
const int N=15;
int r1,r2,n;
db k1,k2,ki,kii;
db k[N];
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        scanf("%d%d%d",&r1,&r2,&n);
        if(r1<r2) swap(r1,r2);
        k1=-1.0/r1;k2=1.0/r2;
        db ans=0,r=0;
        rep(i,1,n+1) {
            if(i==1) {
                r=r1-r2;
                k[1]=1/r;
            } else if(i%2==0) {
                if(i==2) {
                    k[2]=k1+k2+k[1];
                    r=1/k[2];
                } else if(i==4) {
                    k[4]=2*(k1+k2+k[2])-k[1];
                    r=1/k[4];
                    ki=k[2];kii=k[4];
                } else {
                    db tk=2*(k1+k2+kii)-ki;
                    r=1/tk;
                    ki=kii;kii=tk;
                }
            }
            if(r*r<eps) break;
            ans=ans+r*r;
        }
        printf("%.5f\n",ans*pi);
    }
    return 0;
}