F - 三角形

基本信息

题目出处	2022 ICPC 亚洲区域赛南京站
队伍通过率	2/465 (0.4%)

题解

结论

至少需要 \(8\) 个锐角三角形才能构成一个正方形。

证明

把所有用到的点分成以下三类：

• 正方形的 \(4\) 个顶点：这样的点一共 \(4\) 个，每个同时至少是 \(\frac{90}{90}+1=2\) 个三角形的顶点。
• 位于正方形或某个三角形边上（不包括端点）的点：假设这样的点一共 \(x\) 个，每个同时至少是 \(\frac{180}{90}+1=3\) 个三角形的顶点。
• 其余不在正方形或任何一个三角形边上（不包括端点）的点：假设这样的点一共 \(y\) 个，每个同时至少是 \(\frac{360}{90}+1=5\) 个三角形的顶点。

因此有 \(3k\geq 2\times 4+3x+5y\)。另外所有角度之和应该等于所有三角形内角之和，因此 \(180k = 90 \times 4 + 180x + 360y\)，即 \(k=2+x+2y\)。代入前述不等式得 \(y\geq 2\)。

这 \(y\) 个点每个同时至少是 \(5\) 个锐角三角形的顶点，而同时拥有这两个点作为顶点的锐角三角形至多 \(2\) 个，因此一共至少有 \(8\) 个锐角三角形。

构造方案

如果可以将单位正方形划分成 \(k\) 个锐角三角形，那么可以选择任意一个锐角三角形并将其三条边上的中点两两相连，从而得到一个将正方形划分成 \((k+3)\) 个锐角三角形的方案。

证明

这是一道初中数学级别的证明题，还请读者自行证明。

因此，只需要构造出 \(k=8,9,10\) 的例子即可。

参考代码

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

// n = 8, 9, 10 的方案

int A[8][6] = {
    0, 0, 9, 4, 0, 20,
    0, 20, 9, 4, 10, 20,
    10, 20, 9, 4, 11, 4,
    10, 20, 11, 4, 20, 20,
    20, 0, 20, 20, 11, 4,
    0, 0, 10, 0, 9, 4,
    10, 0, 11, 4, 9, 4,
    10, 0, 20, 0, 11, 4
};

int B[9][6] = {
    0, 0, 20, 0, 16, 12,
    0, 0, 16, 12, 0, 20,
    0, 20, 12, 14, 13, 20,
    20, 0, 20, 13, 16, 12,
    16, 16, 16, 12, 20, 13,
    16, 16, 20, 13, 20, 20,
    16, 16, 20, 20, 13, 20,
    16, 16, 13, 20, 12, 14,
    16, 16, 12, 14, 16, 12
};

int C[10][6] = {
    0, 0, 10, 8, 0, 20,
    20, 0, 10, 8, 20, 20,
    0, 20, 10, 8, 20, 20,
    0, 0, 8, 0, 5, 4,
    10, 3, 5, 4, 8, 0, 
    10, 3, 10, 8, 5, 4,
    10, 3, 8, 0, 12, 0,
    10, 3, 12, 0, 15, 4,
    10, 3, 15, 4, 10, 8,
    20, 0, 15, 4, 12, 0
};

void solve(int A[][6], int X, int Y) {
    // 用队列轮流把每个三角形拆成 4 个
    // 每个坐标后面都至少 7 个零，而所有三角形拆一轮数量乘 4，所以拆两轮就够了，无精度问题
    queue<vector<int>> q;
    for (int i = 0; i < X; i++) {
        vector<int> vec;
        for (int j = 0; j < 6; j++) vec.push_back(A[i][j] * ((int) 5e7));
        q.push(vec);
    }

    while (q.size() < Y) {
        vector<int> vec = q.front(); q.pop();
        int x1 = vec[0], y1 = vec[1];
        int x2 = vec[2], y2 = vec[3];
        int x3 = vec[4], y3 = vec[5];
        int x4 = (x1 + x2) / 2, y4 = (y1 + y2) / 2;
        int x5 = (x2 + x3) / 2, y5 = (y2 + y3) / 2;
        int x6 = (x3 + x1) / 2, y6 = (y3 + y1) / 2;
        q.push({x1, y1, x4, y4, x6, y6});
        q.push({x2, y2, x5, y5, x4, y4});
        q.push({x3, y3, x6, y6, x5, y5});
        q.push({x4, y4, x5, y5, x6, y6});
    }

    while (!q.empty()) {
        vector<int> vec = q.front(); q.pop();
        for (int i = 0; i < 6; i++) printf("%d%c", vec[i], "\n "[i < 5]);
    }
}

int main() {
    int n; scanf("%d", &n);
    if (n < 8) {
        printf("No\n");
        return 0;
    }

    printf("Yes\n");
    if (n % 3 == 2) solve(A, 8, n);
    else if (n % 3 == 0) solve(B, 9, n);
    else solve(C, 10, n);
    return 0;
}