P14158 [ICPC 2022 Nanjing R] 三角形题解

唐氏构造题，只需要 CSP-J 2= 的算法水平和初一的课内数学水平就可以做。在草稿纸和几何画板上瞎画可以发现 $n\le 7$ 都无解，但是 $n=8,9,10,11$ 都有解。

下面给出一个~~不太严谨的~~证明：

::::info[证明] 因为正方形有四个顶点，每个顶点的度数都为 $90^\circ$ ，而又因为锐角三角形要求顶点度数 $<90^\circ$ ，所以四个顶点都至少需要被劈一次，这样至少要将平面划分为 $4$ 份，因此 $n<4$ 无解。

然后考虑为什么 $n=4$ 无解：发现此时必然在正方形内部存在一个点是至少一个三角形的顶点，此时这个点交的所有三角形的角度都必须严格小于 $90^\circ$ ，而因为此时最多有四个三角形的顶点平分这个点的度数，根据鸽巢原理可知此时至少有一个顶点的度数 $\ge 90^\circ$ ，显然不符合锐角三角形的条件。

剩下 $n\in\lbrace 5,6,7\rbrace$ 的情况。考虑扩展上面的部分，将所有三角形的顶点分为三类：

点在正方形的顶点上，这里称其为第一类点。
点在正方形的边上，这里称其为第二类点。
点在正方形内部，这里称其为第三类点。

对上面的三类点分别进行考虑：

点在正方形的顶点上：此时该点至少需要被分为 $\lfloor\frac{90^\circ}{90^\circ}\rfloor+1=2$ 个部分。
点在正方形的边上：此时该点至少需要被分为 $\lfloor\frac{180^\circ}{90^\circ}\rfloor+1=3$ 个部分。
点在正方形的内部：此时该点至少需要被分为 $\lfloor\frac{360^\circ}{90^\circ}\rfloor+1=5$ 个部分。

容易证明第一类点必然恰有 $4$ 个，这里设有 $x$ 个第二类点和 $y$ 个第三类点。这里设最少被划分为 $n$ 个三角形，而一个三角形有 $3$ 个顶点，因此可以列出下面的关系式：

$3n\ge 8+3x+5y$

然后还可以从内角和的角度考虑，于是可得下面的等量关系式：

$180n=360+180x+360y$ 即 $n=2+x+2y$

即：

$3n\ge 8+3x+5y$ （ $1$ ）
$n=2+x+2y$ （ $2$ ）

其中 $n,x,y\in\mathbb{N}$ 。

给（ $2$ ）式乘 $3$ ，然后（ $1$ ）式减（ $2$ ）式可得 $0\ge 2-y$ 即 $y\ge 2$ 。此时可以证明 $n<6$ 一定无解。

而 $n\ge 6$ 时，唯一满足（ $2$ ）式的可行情况为 $x=n-6,y=2$ 。发现这个确实满足上面的关系式。但是考虑再换个角度，上面的 $y$ 个点每一个点至少是 $5$ 个不同三角形的顶点，而 $y=2$ 时，最多有两个三角形同时以两个中间的点作为三角形的顶点。因此此时至少有 $5\times 2-2=8$ 个三角形。

此时证明了 $n\le 7$ 时一定无解。而证明 $n\ge 8$ 你只需要给出一组反例即可，下文给出了反例。

::::

然后有经典结论，一个锐角三角形，找到其三条边上的中点两两相连，其必然会形成四个新的三角形，且这四个三角形仍然是锐角三角形。

于是把 $n$ 按照 $\bmod\ 3$ 分类， $n=3k+p$ （ $n\ge 8$ ）都可以规约到 $n=8,n=9,n=10$ 三种情况处理。

然后下面给出三个情况的构造方法（感觉方法应该不少）：

一、 $n=9$

这个是最先构造出来的，所以先写这个了（）

在右上角留一个类似飞镖的结构，左下角部分是一个凸四边形可以切成两个三角形，然后这个时候你只需要保证凸四边形的右上角不在 $y=x$ 直线上，然后不对等的切出五个三角形就行了。

可能描述的不太详细，~~这里直接复制官方题解的图了（）~~

二、 $n=8$

在下半部分切割出来一个等腰梯形，然后底边上取中点就可以割出三个锐角三角形，然后上面两个顶点和正方形上面的两个顶点连边，就又得到了两个三角形。上面同样剩下一个等腰梯形，和下面的方法一样能再割出三个锐角三角形，总共 $8$ 个。

三、 $n=10$

先考虑一个简单的子问题：怎么在一个等腰钝角三角形内割出 $7$ 个锐角三角形。这个时候在底边上取一个中点的方法已经不可行了，考虑对称的取两个点。一个比较直接的方法是直接把两个点和等腰三角形的顶点连起来，但是这样又获得了两个新的钝角三角形，而且还失去了等腰的性质更难处理。

此时可以想到，如果换个方法，在两侧割出两个锐角三角形，剩余部分能否构造出 $5$ 个锐角三角形？发现确实可以构造，中间剩余的部分形如一个五边形，在五边形内部取一点，将其和五边形的五个顶点依次连接，可以得到 $5$ 个锐角三角形。总计 $7$ 个锐角三角形。

问题变为怎么在一个正方形内割出 $3$ 个锐角三角形和一个等腰钝角三角形。这是容易的，找出正方形正中间的竖线，取其下侧一点，将其分别连接正方形的四个顶点即可。下侧的钝角三角形按照刚才的割 $7$ 个锐角三角形的方法构造，总共得到 $10$ 个锐角三角形。

四、扩展到 $n=3k+p$ 的形式

前面已经说过了，可以找到一个锐角三角形三条边中点然后将其两两连接得到 $4$ 个新的锐角三角形，用这个方法可以无限扩展下去。

然后是一些代码实现的细节：因为这个东西不论是大脑思考还是在草稿纸上画都很难不出现误差，所以一个比较好的方法是用 Geogebra 或者 Desmos 这种画图工具来对点进行调整，为了更方便的计算，可以将正方形的横竖方向都均匀的划分为 $20$ 份然后尽量的选择横竖交叉的点来构造。（或许这是这个题场上没几个人过的原因 ~~也有可能大家都不想写这坨石~~）

然后写起来可能比较石，如果少打一个 $0$ 或者打串行了可能就直接爆炸了（）

struct yhb
{
    pair<int, int> p1, p2, p3;
};
int n, dep;
vector<yhb> res, ans;
void gzq(yhb x)
{
    if (dep == n)
    {
        ans.push_back(x);
        return;
    }
    else
    {
        if (x.p1.first % 2 == x.p2.first % 2 && x.p1.first % 2 == x.p3.first % 2 && x.p2.first % 2 == x.p3.first % 2 && x.p1.second % 2 == x.p2.second % 2 && x.p1.second % 2 == x.p3.second % 2 && x.p2.second % 2 == x.p3.second % 2)
        {
            res.push_back({{(x.p1.first + x.p2.first) >> 1, (x.p1.second + x.p2.second) >> 1}, {(x.p1.first + x.p3.first) >> 1, (x.p1.second + x.p3.second) >> 1}, {(x.p2.first + x.p3.first) >> 1, (x.p2.second + x.p3.second) >> 1}});
            res.push_back({x.p1, {(x.p1.first + x.p3.first) >> 1, (x.p1.second + x.p3.second) >> 1}, {(x.p1.first + x.p2.first) >> 1, (x.p1.second + x.p2.second) >> 1}});
            res.push_back({{(x.p2.first + x.p3.first) >> 1, (x.p2.second + x.p3.second) >> 1}, x.p2, {(x.p1.first + x.p2.first) >> 1, (x.p1.second + x.p2.second) >> 1}});
            res.push_back({{(x.p2.first + x.p3.first) >> 1, (x.p2.second + x.p3.second) >> 1}, {(x.p1.first + x.p3.first) >> 1, (x.p1.second + x.p3.second) >> 1}, x.p3});
            dep += 3;
        }
        else
            ans.push_back(x);
    }
}
int32_t main()
{
    // freopen(".out","w",stdout);
    cin >> n;
    dep = 0;
    if (n < 8)
    {
        cout << "No\n";
        return 0;
    }
    if (n % 3 == 0)
    {
        res.push_back({{1000000000, 650000000}, {800000000, 600000000}, {1000000000, 0}});
        res.push_back({{1000000000, 650000000}, {800000000, 600000000}, {800000000, 800000000}});
        res.push_back({{1000000000, 650000000}, {1000000000, 1000000000}, {800000000, 800000000}});
        res.push_back({{0, 0}, {800000000, 600000000}, {1000000000, 0}});
        res.push_back({{699999999, 1000000000}, {1000000000, 1000000000}, {800000000, 800000000}});
        res.push_back({{699999999, 1000000000}, {600000000, 700000000}, {800000000, 800000000}});
        res.push_back({{699999999, 1000000000}, {0, 1000000000}, {600000000, 700000000}});
        res.push_back({{800000000, 600000000}, {600000000, 700000000}, {800000000, 800000000}});
        res.push_back({{0, 0}, {800000000, 600000000}, {0, 1000000000}});
    }
    else if (n % 3 == 1)
    {
        res.push_back({{0, 0}, {150000000, 150000000}, {0, 250000000}});
        res.push_back({{0, 0}, {150000000, 150000000}, {250000000, 0}});
        res.push_back({{300000000, 200000000}, {1000000000, 0}, {250000000, 0}});
        res.push_back({{200000000, 300000000}, {0, 1000000000}, {0, 250000000}});
        res.push_back({{300000000, 200000000}, {1000000000, 0}, {1000000000, 1000000000}});
        res.push_back({{200000000, 300000000}, {0, 1000000000}, {1000000000, 1000000000}});
        res.push_back({{150000000, 150000000}, {300000000, 200000000}, {200000000, 300000000}});
        res.push_back({{1000000000, 1000000000}, {300000000, 200000000}, {200000000, 300000000}});
        res.push_back({{300000000, 200000000}, {150000000, 150000000}, {250000000, 0}});
        res.push_back({{200000000, 300000000}, {150000000, 150000000}, {0, 250000000}});
    }
    else
    {
        res.push_back({{500000000, 1000000000}, {0, 1000000000}, {450000000, 800000000}});
        res.push_back({{500000000, 1000000000}, {1000000000, 1000000000}, {550000000, 800000000}});
        res.push_back({{0, 0}, {0, 1000000000}, {450000000, 800000000}});
        res.push_back({{1000000000, 0}, {1000000000, 1000000000}, {550000000, 800000000}});
        res.push_back({{0, 0}, {500000000, 0}, {450000000, 800000000}});
        res.push_back({{500000000, 1000000000}, {450000000, 800000000}, {550000000, 800000000}});
        res.push_back({{1000000000, 0}, {500000000, 0}, {550000000, 800000000}});
        res.push_back({{500000000, 0}, {450000000, 800000000}, {550000000, 800000000}});
    }
    n -= ((n % 3 == 0) ? 9 : ((n % 3 == 1 ? 10 : 8)));
    for (int i = 0; i < res.size(); i++)
        gzq(res[i]);
    cout << "Yes" << endl;
    for (int i = 0; i < ans.size(); i++)
    {
        pair<int, int> p1 = ans[i].p1, p2 = ans[i].p2, p3 = ans[i].p3;
        cout << p1.first << ' ' << p1.second << ' ' << p2.first << ' ' << p2.second << ' ' << p3.first << ' ' << p3.second << endl;
    }
}

std 写的好像更加美观简洁容易调一些，所以在这里也贴一下 std：

#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;
}

隐藏／恢复文章

随机文章

P14158 [ICPC 2022 Nanjing R] 三角形 题解

随机文章

P14158 [ICPC 2022 Nanjing R] 三角形题解