はまやんはまやんはまやん

hamayanhamayan's blog

NN and the Optical Illusion [Codeforces Round #532 (Div. 2) C]

https://codeforces.com/contest/1100/problem/C

中心に半径rの円がある。
この円の周りに半径Rの円をN個敷き詰めたい。
半径Rを求めよ。

N,R≦100

 
 
 
 
 
 
 
 
 
 
 
 

解説

https://codeforces.com/contest/1100/submission/48337940

以下の説明では、内側の半径がR, 外側の半径がrとして説明している。
(プログラムコードがそうなってしまってた)
 
二分探索する。
check(r) := 外側の半径をrとして並べたときに隙間ができるか
隙間ができるかということなので、重なりができる場合はtrueとなる。
f:id:hamayanhamayan:20190114112240p:plain
このような図を考える。
余弦定理から、R,r,Nがわかっていれば、2rの地点の長さが計算できる。

(2 * r)^2 = 2(r + R)^2 - 2*(r + R)^2 cos(2PI / N)

左辺をp, 右辺のdとしたときに、隙間ができない状況というのは、
p≧dの場合である。
これは余弦定理的にはsqrt(d)だけ間隔があるが、その長さが2rを下回っているので、被っている領域があると判断できるということ。
 
自分は精度計算が分からなかったので、[0,10^9]の範囲をlong doubleを使って計算した。
ここは適当なので注意。

typedef long double ld;
ld N, R;
//---------------------------------------------------------------------------------------------------
const ld EPS = 1e-8, INF = 1e12, PI = 2 * acos(0.0);
bool check(ld r) {
    // (2 * r)^2 = 2(r + R)^2 - 2*(r + R)^2 cos(2PI / N)
    ld rR = r + R;
    ld d = 2 * rR * rR - 2 * rR * rR * cos(2 * PI / N);

    ld p = (2 * r)*(2 * r);


    return p >= d;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> R;
    double ng = 0, ok = 1e9;
    rep(i, 0, 50) {
        double md = (ng + ok) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }
    printf("%.10f\n", ok);
}