“蔚来杯“2022牛客暑期多校训练营4 L.Black Hole 垃圾计算几何

L.Black Hole

题目大意

给定正$n$面体(不一定合法，不合法就impossible)，边长为$a$，进行$k$次操作，每次操作取正多面体几何中心连线生成新凸壳。问$K$次操作后生成的是否为正多面体，以及最终正多面体的边长。

首先，合法的正多面体只有：正四面体、正六面体、正八面体、正十二面体、正二十面体。

• 正四面体只能生成正四面体
• 正六面体操作奇数次可以生成正八面体，偶数次生成正六面体
• 正八面体操作奇数次可以生成正六面体，偶数次生成正八面体
• 正十二面体操作奇数次可以生成正二十面体，偶数次生成正十二面体
• 正二十面体操作奇数次可以生成正十二面体，偶数次生成正二十面体

接下来讨论边长变化规律：可以发现两次生成的边长关系可以由原体的内切球和生成体的外接球关系导出，因为这俩球是同一个球。那么首先我们整理一下边长$a$与球半径$r$关系公式：

那么我们可以推出转换关系：

• 正四面体$\to$正四面体：$\frac{a_2}{a_1}=\frac{1}{3}$
• 正六面体$\to$正八面体：$\frac{a_2}{a_1}=\frac{1}{\sqrt{2}}$
• 正八面体$\to$正六面体：$\frac{a_2}{a_1}=\frac{\sqrt{2}}{3}$
• 正十二面体$\to$正二十面体：$\frac{a_2}{a_1}=\frac{{\phi }^2}{\sqrt{3-\phi }\times \sqrt{2\sqrt{5}+10}}$
• 正二十面体$\to$正十二面体：$\frac{a_2}{a_1}=\frac{\sqrt{5}+3}{6\phi }$

至此，可以通过递推得到答案。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define double long double
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

double K[20];
int nxt[20], n, k;
double a;
void init(){
    cout << fixed << setprecision(12);
    K[4] = 1.0 / 3;
    double fi = (1 + sqrtl(5)) / 2;
    K[6] = sqrtl(2) / 2;
    K[8] = sqrtl(2) / 3;
    K[12] = 2 * fi / sqrtl(3 - fi) * fi / sqrtl(10 + 2 * sqrtl(5));
    K[20] = (3 + sqrtl(5)) / 6 / fi;
    nxt[4] = 4, nxt[6] = 8, nxt[8] = 6, nxt[12] = 20, nxt[20] = 12;
}


inline void solve(){
    cin >> n >> a >> k;
    if(n != 4 && n != 6 && n != 8 && n != 12 && n != 20){
        cout << "impossible\n";
        return;
    }

    for(int i = 1; i <= k; i++){
        a *= K[n], n = nxt[n];
    }
    cout << "possible "<<n<<" "<<a<<endl;
}
signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    init();
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}
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
36
37
38
39
40
41
42
43
44