CF213D Stars 题解

myEnd · 2021-12-11 23:23:11 · 题解

本题解全部图片均由 Desmos 图形计算器绘制而成。

回归正题

原题链接

题解

首先我们可以以 (0,0)，即坐标系原点构造为起点构造一个符合题意的“五角星”，如下图所示：

前往 Desmos 查看此图 -> 链接

所构造的该五边形的五个顶点及其坐标分别为（保留了 15 位小数）：

怎么得到的？把给定的样例的每对 (x,y) 都减去原点的那对，再把它用你的计几模板旋转一下，让我们可爱的 E 点在 x 轴上。

注意到下一个五角星其实就是把 A、B、C、D 四个点平移，让 A 与 E 重合即可，所以我们在输出时每次分别加上线段 AE 的距离即可。

接下来我们来找寻规律。对于这种旋转的题，很容易知道 x 坐标应当跟 \sin 函数有关系，y 坐标跟 \cos 函数有关系。而考虑到旋转要在 \sin 和 \cos 函数的表达式中转化为弧度，所以肯定跟 \pi 有关。那么直接开始试系数会比你手推简单的很多。

其实如果你要手推的话，你会得到对于任意一个“拐角”处，如 \angle ADE 为 36\degree，而实际上你转化成弧度的角度应当是 90\degree - 36\degree = 54\degree。如果脑子比较好的同学，绕弯能力比较强，可以理解一下为啥，理解不了的也没关系，NOI 系列的比赛都会给你提供 python 的支持，你可以使用 python 来代替你计算 \sin 等函数的值以便你更快的试系数，然后画图可以使用 python 自带的海龟作图，具体就不细讲了。当然如果是打 CF 之类的，还是建议使用 Desmos 这样的比较好用的数学专用的计算器，会方便很多，类似的软件还有几何画板、Geogebra 等。

好了，接下来讲解如何试系数。我们知道这道题对于每个点的坐标，应当这样去找寻规律：(\dfrac{x}{\sin(k \cdot \pi)}, \dfrac{y}{\cos(k \cdot \pi)}) ，因为显然对于每一个点的 x 坐标（y 坐标），一定是有一个系数 m 乘以 \sin(k \cdot \pi) （乘以 \cos(k \cdot \pi)） 得到的，所以我们只要找到 (\dfrac{x}{\sin(k \cdot \pi)}, \dfrac{y}{\cos(k \cdot \pi)}) 这个玩意的规律即可。

1. 先看 A 点，原点，没啥好说的，不用找规律了。

2. 再看 B 点，开始试，首先由于是 D 题我们知道一定 \sin（\cos） 函数的参数 \pi 的系数 k 一定是保留一位小数即可得到的，又容易知道这个 k 一定是小于 2 的，我们直接和点 C 的 x 坐标对比着看会比较好。

3. 首先知道 \sin \pi=0，分母不能为 0，所以这个 pass 掉。

4. 我们先来把其余的分为四个区间：(0, 0.5), (0.5, 1), (1, 1.5), (1.5, 2) 以及几个特殊值：0.5, 1, 1.5, 2。首先来看我们在 Desmos 的左侧（我称之为“计算区”）输入 k=0.5 代表接下来要试的系数是 0.5，然后依次键入：B.x/sin(kpi)[Enter]C.x/sin(kpi)，得到如下图所示的结果即证明你成功了：

5. 真不错，接下来注意到这俩没关系，我们就直接 pass，试着尝试 1、1.5、2，容易注意到在 k 取整数的时候其实是未定式（undefined），代表你此时的式子无法计算，如分母为 0。接下来我们就可以考虑每个开区间了，首先由 \sin 函数的对称性我们可以知道直接试 (0,0.5) 以及 (0.5,1) 即可，其余的其实就是在其前面加个 - 号。

6. 首先我们注意到在 k 取到 0.3 和 0.7 时出现了我们题目中给定的数：10，也是我们正五边形的边长，就说明这两个数中有一个就是我们所求的，然后发现另外的两个点是黄金分割比 \frac{\sqrt{5}+1}{2} 的倍数，所以规律没错。而在计算结果中这两个数所求得的结果是一样的，所以把其他的两个点的坐标也看一下，发现确实一样，但是点 D 的数很奇怪，所以我们不妨一会再看（其实它在一个奇妙的论文中出现了：链接，提到了黄金比例，而 B 点的坐标也跟黄金比例有关，所以这里就说明其实数是正确的）。

7. 看 y 坐标，我们把所有的 \sin 都改为 \cos、y 都改为 x，发现这两个数只是对 B 和 D 两点的 y 坐标取反了，为了方便，我们这里不妨取那个没取反的：k=0.3。接下来要讨论那个烦人的 D 点的 x 坐标了。

8. 考虑到这个奇葩的数已经无法跟 k 建立关系了，我们考虑和其他的点相加求和再除以 \sin(k \cdot \pi) 来得到想要的结果，如 10、20。显然与点 A 无关，然后试到点 B 和它相加时发现了规律，然后再看剩余的点（不考虑点 E）又没有规律，所以我们就知道应当是与点 B 求和找到规律。（如果你脑子够好，可以给它重配系数 k，在取到 k=0.1 时发现规律。）

9. 综上，我们已经试完系数并发现规律了，接下来解决输出问题，这都是代码部分了，其实这里就是模拟，思路也很简单，对于每次我们把 A、B、C、D 平移到直到点 A 在点 E 的位置，即每个点的 x 坐标都加线段 AE 的长度即可。

实现代码的思路是这样的：先求出点 A、B、C、D 的坐标，之后四个一周期输出，每次输出后加上 AE，一共应当是 4n+1 个点，然后顺序啥的也很好解决，这里就不再赘述了。

说句实话，要想 AC 这道题，你们完全可以抄我的数据，但是我觉得搞明白其中的道理，也就是怎么试系数，这才是最重要的。所以，为了锻炼一下你自己的能力，也为打造一个更好的洛谷，动一动脑筋吧！

    cin >> n;
    cout << (n<<2)+1 << endl;

    for(int i=0; i<(n<<2)+1; ++i)
        cout << x[i%4] << ' ' << y[i%4] << endl, x[i%4]+=d/*10 倍的黄金分割比，也是我们配出的那个系数后算出的函数值中的一个，最开始的线段 AE 的距离*/;

    for(int i=0; i<n; ++i)
        cout << (1+(i<<2)) << ' ' << (3+(i<<2)) << ' ' << (5+(i<<2)) << ' ' << (2+(i<<2)) << ' ' << (4+(i<<2)) << endl; 

    for(int i=0; i<n; ++i)
        cout << (1+(i<<2)) << ' ' << (2+(i<<2)) << ' ' << (3+(i<<2)) << ' ' << (4+(i<<2)) << ' ';

    for(int i=0; i<=n; ++i)
        cout << ((n-i)<<2)+1 << ' ';

最后，祝你们都能通过此题！