G. Geometric Balance 详细题解

题意梳理

乌龟在平面上行动，支持三种指令：

1. rotate a：逆时针旋转$a$度，保证$a$是$45$的倍数，仅朝向8个方位；
2. draw d：朝当前方向画长度为$d$的线段，记录墨水覆盖路径；
3. move d：朝当前方向移动$d$，不留下痕迹。

求最小正整数角度$b$，满足：将乌龟任意平移位置、整体旋转$b^\circ$后，原样执行所有指令，画出的墨水点集与原图完全一致。

核心结论

1. 合法旋转角只能是$45^\circ$的倍数：$45^\circ,90^\circ,135^\circ,\dots,360^\circ$；
2. $360^\circ$一定是合法解，题目保证答案存在；
3. 只需提取所有draw生成的线段端点，图案旋转$b^\circ$后整体平移能与原图案完全重合，则$b$合法；
4. 从小到大枚举角度，第一个合法角度即为答案。

方向建模

将8个45°朝向编号$0\sim7$，对应单位方向向量：

$$\begin{align*} 0&: (1,0)\quad(0^\circ)\\ 1&: (1,1)\quad(45^\circ)\\ 2&: (0,1)\quad(90^\circ)\\ 3&: (-1,1)\quad(135^\circ)\\ 4&: (-1,0)\quad(180^\circ)\\ 5&: (-1,-1)\quad(225^\circ)\\ 6&: (0,-1)\quad(270^\circ)\\ 7&: (1,-1)\quad(315^\circ) \end{align*} $$

每次旋转$a$度，等价于朝向编号增加$\dfrac{a}{45}$，对$8$取模更新朝向。

模拟过程

1. 初始位置$(0,0)$，初始朝向编号$dr=0$；
2. 遍历所有指令：
   • 旋转指令：更新朝向$dr=(dr+\frac{a}{45})\bmod 8$；
   • 移动/绘制指令：根据当前朝向算出终点坐标；
   • 仅draw指令存入线段起点、终点，move不记录图案信息；
3. 最终得到原图所有墨水端点集合$P$。

旋转重合判定原理

设候选旋转角度为$b$，对应弧度$\theta=\dfrac{b\cdot\pi}{180}$。 平面点$p(x,y)$逆时针旋转$\theta$后的坐标公式：

$$\begin{cases} x' = x\cos\theta - y\sin\theta\\ y' = x\sin\theta + y\cos\theta \end{cases} $$

判定规则：

1. 取集合内第一个点$p_0$，旋转得到$p_0'$；
2. 求出唯一固定平移量：

$$dx = p_0.x - p_0'.x,\quad dy = p_0.y - p_0'.y$$

3. 对集合内所有点，旋转后加上平移量$(dx,dy)$，若都能与原点点重合，则角度$b$合法。

枚举策略

按$b=45,90,135,\dots,360$从小到大依次验证，第一个满足条件的角度就是最小答案。

复杂度分析

• 指令总数$n\le 5\times 10^4$，模拟遍历$O(n)$；
• draw指令最多$2000$条，总端点数量$k\le 4000$；
• 最多枚举$8$种角度，总复杂度$O(n+8k)$，时间完全满足$3\mathrm{s}$限制。

样例解析

样例1

输入仅一条draw 10，只有一条线段。

• 旋转$180^\circ$后平移可与原线段重合，更小角度不满足，输出$\boldsymbol{180}$。

样例2

连续四次转$90^\circ$绘制，构成正方形。

• 旋转$90^\circ$即可整体重合，输出$\boldsymbol{90}$。

样例3

两段长度不同、位置错开的线段，无小于$360^\circ$的对称角度，输出$\boldsymbol{360}$。

代码核心细节

1. 用double存储坐标，设置精度误差$\mathrm{EPS}=10^{-8}$进行浮点数判等；
2. sgn函数统一处理浮点正负与相等判断，避免精度出错；
3. 仅保存绘制端点，舍弃无效移动路径，精简判定集合；
4. 枚举顺序严格从小到大，保证最先找到最小合法角度。

易错点

1. 不能只判定线段重合，必须判定所有端点整体旋转平移重合；
2. 旋转为逆时针，公式不可写反；
3. 朝向更新必须对$8$取模，防止朝向编号越界；
4. 不可忽略平移量，仅原点旋转无法满足题目题意。