Project Euler - Problem 587

concave triangle

　半径の等しい円を横に n 個並べ，長方形で覆う．左下と右上を結ぶ対角線を引く．

左下部分に着目し，L-section および concave triangle を定義．

Q. concave triangle の面積が L-section の面積の 0.1% 未満となるような最小の n はいくつか？

A.

円の半径を 1 として，長方形の左下を原点とした座標系を定める．

$\angle ABP = \theta $ とおいて，点 P を n と θ で表す．連立方程式

$$ \left \{ \begin{array}{rl} &y = \frac{1}{n} x \\ &(x - 1)^{2} + (y - 1)^{2} = 1 \end{array} \right. $$

を解いて，x 座標の小さいものを選び $ \displaystyle \text{P} \left(\frac{n (\sqrt{n} - 1)^{2}}{n^{2} + 1}, \frac{ (\sqrt{n} - 1)^{2} }{ n^{2} - 1 }\right). $

これと $\text{P}(1-\sin \theta, 1-\cos \theta)$ より， $ \displaystyle \theta = \sin^{-1} \left( \frac{n \sqrt{2n} - n + 1}{n^{2} + 1} \right) $ が従う．

concave triangle の面積は

$$ \begin{align} \text{(concave triangle の面積)} &= \text{(△OAP の面積) + (△BAP の面積) - (扇形 BAP の面積)} \\[5pt] &= \underbrace{\frac{1}{2}(1 - \cos \theta)}_{△OAP} + \underbrace{\frac{1}{2} \sin \theta}_{△BAP} - \underbrace{\frac{1}{2} \theta}_{扇形BAP} \\ &= \frac{1}{2} (1 + \sin \theta - \cos \theta - \theta) \end{align} $$
と計算できる．L-section の面積は $ \displaystyle 1 - \frac{\pi}{4} $ だから，

$$ \displaystyle \frac{ \text{(concave triangle の面積)} }{ \text{(L-section の面積)} } = \frac{ 2(1 + \sin \theta - \cos \theta - \theta) }{ 4 - \pi } < 0.001. $$

これを満たすような最小の n を求めればよい．

#include <iostream>
#include <cmath>

using namespace std;

double concave(int n) {
    double sin, cos, theta, ratio;
    sin = (n * sqrt(2 * n) - n + 1) / (n * n + 1);
    cos = (sqrt(2 * n) + n * n - n) / (n * n + 1);
    theta = asin(sin);

    ratio = (2 * (1 + sin - cos - theta)) / (4 - M_PI);
    return ratio;
}

void PE0587() {
    int ans = 1;
    while (concave(ans) > 0.001) {
        ans++;
    }
    cout << ans << endl;
}

int main()
{
    PE0587();
    return 0;
}

練習も兼ねてダラダラ書いたら時間めっちゃ溶けた，時間ドブに捨てるの好きすぎる．