kmjp's blog

競技プログラミング参加記です

yukicoder : No.724 円と円の間の円

yukicoder

このテク使うのまだ２回目…。
https://yukicoder.me/problems/no/724

問題

整数n,a,bが与えられる。a＜bである。
２次元座標で(a,0)を中心とする半径aの円と(b,0)を中心とする半径bの円を考える。
前者に外接し、後者に内接する円を、互いに重ならないようにn個配置する。
n個の半径の最小値を最大化せよ。

解法

Editorialに反転幾何による式が書いてあるので、それを導いてみる。
２つの円を原点に対し反転するとY軸に平行な2つの直線 \displaystyle x = \frac{1}{2a}と \displaystyle x = \frac{1}{2b}になる。

ここで両者の間に、X軸に近い位置にn個円を配置することを考える。
各円のX座標は X=\frac{1}{4}\left( \frac{1}{a} + \frac{1}{b} \right)であり、半径はいずれも R=\frac{1}{4}\left( \frac{1}{a} - \frac{1}{b} \right)となる。
もっともY座標が大きい位置の円の中心のY座標は Y=(n-1)Rとなる。
この円について、最も原点に近い位置までの距離は \sqrt{X^2+Y^2} - Rであり遠い点までの距離は \sqrt{X^2+Y^2} + Rとなる。
よってこの２点を再度反転させると、両者の距離の半分が元図形における円の半径となるので、求める解は \frac{1}{2}\left( \frac{1}{\sqrt{X^2+Y^2} - R} - \frac{1}{\sqrt{X^2+Y^2} + R} \right)である。
X,Y,Rは上に書いた通りで、これを整理するとEditorialにある \frac{4ab(b-a)}{(n^2-2n)(b-a)^2+(a+b)^2}が得られる。

void solve() {
	double N,A,B;
	
	cin>>N>>A>>B;
	_P("%.12lf\n",4*A*B*(B-A)/((N*N-2*N)*(B-A)*(B-A)+(A+B)*(A+B)));
}

まとめ

反転幾何使うの、KUPC2016の最終問以来な気がする。
百目おばけ(解説PDF)