KUPC2016 : K - 百目おばけ / Hundred Eyes Monster

これは思いつかないわ…。
http://kupc2016.contest.atcoder.jp/tasks/kupc2016_k

問題

２次元座標上で互いに共通部分を持たない２つの円が与えられる。
両者に接し、かつ互いに共通部分を持たない円をできるだけ多く追加したい。
最大何個の円を置けるか。

解法

反転を行うと円と直線を相互変換できる。
反転を２回行い、２つの円を同心円となるようにしよう。
１回目で片方の円を直線に変換するようにし、２回目で両者の変換後の円の中心が一致するように反転する。

２つの円を同心円にできれば、両者の間に何個円が配置できるかは、１個の円を置く際の偏角の大きさで簡単に求められる。

int T;
double XA,YA,RA;
double XB,YB,RB;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>XA>>YA>>RA;
		cin>>XB>>YB>>RB;
		double D=hypot(XA-XB,YA-YB);
		
		double X=0.5/RA;
		double r1=X-1/(RA+D-RB);
		double r2=X-1/(RA+D+RB);
		
		double x = sqrt(r1*r2);
		double r3 = 0.5/x;
		double a = 0.5/(x-r1);
		double b = 0.5/(x-r2);
		double r4 = abs(a-b);
		
		double dif=(r4-r3)/2;
		double at = asin(dif/(r3+dif));
		_P("%d\n",(int)(atan(1)*4/at));
	}
}

まとめ

反転幾何を知らなかったので解きようがなかった。