Not So Simple Polygon Embedding

发表于 更新于 分类于 ，

    给出一个2n正多边形，边长为1，n为奇数。

    求最小外接正方形的边长。

Not So Simple Polygon Embedding

Created by LXC on Mon Nov 6 12:37:03 2023

https://codeforces.com/problemset/problem/1354/C2

ranting: 2000

tag: binary search, brute force, geometry, math

problem

给出一个2n正多边形，边长为1，n为奇数。

求最小外接正方形的边长。

solution

我们让多边形的直径成为正方形的边长。这是最大的边长。
然后旋转多边形，可以让正方形边长减少。

由于中心对称，绕中心旋转$\frac{2\pi}{2n} = \frac{\pi}{n}$将回到原来的图形。由于对称性可旋转的角度应该在$[0,\frac{\pi}{2n}]$。

我们算出多变形的直径为$\frac{1}{\sin(\frac{\pi}{2n})}$，初始时外接正方形的边长就是多边形的直径
设旋转角度为x，外接正方形的边长将为$\frac{\cos(x)}{\sin(\frac{\pi}{2n})}$

我们的目标就是在$x \in [0, \frac{\pi}{2n}]$，求$\frac{\cos(x)}{\sin(\frac{\pi}{2n})}$最小值。

应该只有一个波谷，可以利用三分法求出最小边长。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    double pi = atan(1) * 4;
    double EPS = 1e-9, R = pi / (2 * n);
    auto cal = [&](double x) -> double { return fabs(cos(x) / sin(R)); };
    cout << cal(pi / (4 * n)) << endl;
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}