题目理解

我们有一个由 $N$ 个顶点组成的正交多边形（每条边平行于坐标轴，相邻边垂直）。需要判断是否存在一条水平或垂直线段，将多边形分割成两个全等的部分，且分割线完全在多边形内部（只有端点接触边界）。

问题转化

多边形是正交的，因此可能的切割线只能是水平或垂直的。我们需要：

1. 找到所有可能的分割线候选
2. 对每个候选，验证分割后的两部分是否全等
3. 输出最小的合法分割线

关键思路

1. 扫描线算法

代码使用扫描线算法来寻找垂直分割线候选：

• 按 x 坐标扫描多边形
• 维护当前与扫描线相交的水平边
• 当两条水平边在扫描线上对称时，它们可能形成分割线

2. 周长编码

为快速判断对称性，将多边形周长编码为数字序列：

• 每个顶点分配一个基于周长的唯一ID
• 通过ID差值的比较来判断对称位置

3. 几何变换验证

对于每个候选分割线，将多边形分割为两部分后，通过几何变换验证全等：

• 平移、旋转、反射
• 比较顶点序列是否相同

算法步骤

1. 预处理

// 计算周长编码
num[0] = 0;
for (int i = 1; i <= len; i++)
    num[i] = num[i - 1] + abs(p[i % len].first - p[i - 1].first) + 
             abs(p[i % len].second - p[i - 1].second);

2. 事件扫描

// 为每条水平边创建事件
for (int i = 0; i < len; i++) {
    int ni = (i + 1) % len;
    if (p[i].second == p[ni].second)
        if (p[i].first < p[ni].first)
            insertEvents(p, p[i].second, i, ni, 1);  // 进入边
        else
            insertEvents(p, p[i].second, ni, i, -1); // 离开边
}

3. 候选生成

在扫描过程中，当两条水平边满足对称条件时生成候选：

ll did = el.delt == 1 ? id1 - id2 : id2 - id1;
if (did < 0) did += num[len];
ll grow = (num[len] / 2 - did) / 2;

if (grow <= cangrow && 2 * (did + 2 * grow) == num[len])
    Spl.insert(line(curx + grow, min(el.y, it->y), max(el.y, it->y)));

4. 全等验证

对每个候选分割线，分割多边形并验证：

Split(p, len, it->x, it->y1, it->y2, a, alen, b, blen);
if (complexCompare(a, alen, b, blen)) {
    x = it->x; y1 = it->y1; y2 = it->y2;
    return true;
}

全等比较算法

1. 标准化

void Move(ii p[], int len, int &nil) {
    nil = 0;
    for (int i = 0; i < len; i++)
        if (p[i] < p[nil]) nil = i;
    
    ii d = ii(-p[nil].first, -p[nil].second);
    for (int i = 0; i < len; i++)
        p[i] = ii(p[i].first + d.first, p[i].second + d.second);
}

2. 旋转和反射测试

bool spinAround(ii a[], int alen, int anil, ii b[], int blen) {
    int bnil;
    for (int i = 0; i < Maxr; i++) {  // 测试4个旋转角度
        Rotate(b, blen);
        Move(b, blen, bnil);
        if (trivialCompare(a, alen, anil, b, blen, bnil))
            return true;
    }
    return false;
}

复杂度分析

• 时间复杂度：$O(N \log N + K \cdot N)$，其中 $K$ 是候选分割线数量
• 空间复杂度：$O(N)$

算法标签

• 计算几何
• 扫描线算法
• 多边形分割
• 几何变换
• 全等判断

总结

本题通过扫描线算法高效地找到可能的分割线候选，利用周长编码快速筛选对称边，最后通过几何变换验证分割后的两部分是否全等。算法充分利用了正交多边形的特性，在 $O(N \log N)$ 时间内解决问题。