问题分析

我们需要计算一个简单多边形（无自交）的对称轴数量。对称轴是一条直线，将多边形映射到自身。

关键思路

1. 对称轴的几何性质

对于多边形，对称轴可能是：

• 顶点-顶点对称轴：通过两个相对的顶点
• 顶点-边中点对称轴：通过一个顶点和一条对边的中点
• 边中点-边中点对称轴：通过两条对边的中点

2. 问题转化

将几何问题转化为字符串回文问题：

• 把多边形表示为一个环状序列
• 对称轴对应环上的某种"回文"性质
• 使用 Manacher 算法在环上寻找所有可能的对称轴

3. 算法框架

步骤 1：构造扩展序列

// 原始顶点: p[0], p[2], p[4], ... (2i)
// 边中点: p[1], p[3], p[5], ... (2i+1)
for (int i = 1; i < n2; i += 2)
    p[i] = p[i - 1] + p[i + 1];  // 计算边中点

这样构造了一个长度为 2n 的环状序列，包含顶点和边中点。

步骤 2：坐标缩放

for (int i = 0; i != n2; i += 2)
    p[i] = p[i] + p[i];  // 顶点坐标乘以2

避免浮点数运算，所有计算使用整数。

步骤 3：Manacher 算法在环上的应用

核心检查函数：

bool check(const Vec2D &u, const Vec2D &to, const Vec2D &l, const Vec2D &r) {
    return (l - u).len_2() == (r - u).len_2() && !(r - l).dot(to);
}

检查条件：

1. (l - u).len_2() == (r - u).len_2()：两点到对称轴上某点的距离相等
2. !(r - l).dot(to)：两点连线与对称轴垂直

步骤 4：环状序列处理技巧

// 将环展开为3倍长度的线性序列
int n3 = n2 * 3;
for (int i = 0; i < n3; i++) {
    const Vec2D &u = at(i);  // at(k) = p[k % n2]
    // ... Manacher 扩展
}

通过3倍展开，可以处理环状序列的回文性质。

算法详细解析

向量运算基础

struct Vec2D {
    int x, y;
    // 向量加减
    auto operator + (const Vec2D &r) const -> Vec2D;
    auto operator - (const Vec2D &r) const -> Vec2D;
    // 点积
    auto dot(const Vec2D &r) const -> i64;
    // 长度平方
    auto len_2() const -> i64;
    // 旋转90度（求垂直向量）
    auto rotate_90() const -> Vec2D;
};

Manacher 算法在几何上的应用

标准的 Manacher 算法检查字符相等，这里改为检查几何对称性：

while (r[i] != i && i + r[i] + 1 != n3 && 
       check(u, to, at(i - r[i] - 1), at(i + r[i] + 1)))
    r[i]++;  // 暴力扩展

对于位置 i：

• u 是对称轴上的点
• to 是对称轴的方向向量
• 检查 i-r[i]-1 和 i+r[i]+1 是否关于该轴对称

对称轴计数

return std::accumulate(r + n2, r + (n2 << 1), 0, [](const int sum, const int v) {
    return sum + (v >= n2);
}) >> 1;

只统计中间段（第二份拷贝）中回文半径 ≥ n2 的位置，除以2避免重复计数。

复杂度分析

• 时间复杂度：$O(n)$
  • Manacher 算法是线性的
  • 每个位置最多被扩展一次
• 空间复杂度：$O(n)$
  • 存储多边形点和回文半径数组

样例分析

样例1：12个点的多边形

输出4条对称轴，对应一个近似十字形的对称图形。

样例2：6个点的多边形

输出2条对称轴，对应一个中心对称的六边形。

算法优势

1. 通用性：适用于任意简单多边形，不限于凸多边形
2. 效率：$O(n)$ 时间复杂度，处理 $n \leq 100,000$ 的数据规模
3. 数值稳定性：全程整数运算，避免浮点误差

总结

本题通过巧妙的几何到字符串的转化，将多边形对称轴问题转化为环状序列的回文问题，再利用扩展的 Manacher 算法高效解决。这种"几何问题→字符串匹配"的思路在计算几何中非常有用。

核心技巧：

• 顶点和边中点交替表示
• 环状序列的3倍展开
• 几何对称性的代数化表达
• Manacher 算法在自定义相等检查下的应用