40. CF-Not So Simple Polygon Embedding

标签：frac Polygon Simple dfrac CF 4n 2n pi sin

链接

题解里的几何做法很巧妙，这里记录一下。

因为有 \(2n\) 条边，每条边对应的角度就是 \(\dfrac{2\pi}{2n}\)。

考虑对角线与底边平行的状态。顺时针或逆时针转动 \(\dfrac{\pi}{2n}\) 的角度后，对角线会与底边垂直，这就还原成了最开始的状态。

然后因为顺时针和逆时针转是一样的，所以最优解应该在中间取到。

此时旋转的角度为 \(\dfrac{\pi}{4n}\)。取多边形中心 \(O\)，向底边作垂线，可以得到

\[\frac{1}{2}d=r\cos(\frac{\pi}{4n}) \]

其中 \(d\) 就是所求的正方形边长，然后 \(r\) 是多边形顶点到中心的距离。

显然

\[\sin(\frac{\pi}{2n})=\frac{1}{2r} \]

所以答案就是 \(\dfrac{\cos(\frac{\pi}{4n})}{\sin(\frac{\pi}{2n})}\)，即 \(\dfrac{1}{2}\sin(\dfrac{\pi}{4n})\)。

#include <bits/stdc++.h>
using namespace std;

const double pi = acos(-1);

void solve() {
    int n;
    cin >> n;
    cout << 0.5 / sin(pi / (4 * n)) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    cout << fixed << setprecision(10);
    while (T--) {
        solve();
    }
}

标签：frac,Polygon,Simple,dfrac,CF,4n,2n,pi,sin
From： https://www.cnblogs.com/theophania/p/p40.html