一、问题分析

1.1 问题描述

给定两个等面积的简单多边形 $S$ 和 $T$，通过剪刀（分割）和胶带（拼接）操作，将 $S$ 变换成 $T$。

操作限制：

• 只能进行平移和旋转，不能镜像翻转
• 点的顺序必须保持一致（逆时针）
• 最终形状必须与 $T$ 等价

1.2 数学基础

Wallace-Bolyai-Gerwien 定理：

任意两个等面积的多边形可以通过有限次剪切和重新拼接互相转换。

证明思路：

1. 任意多边形可以剖分成三角形
2. 任意三角形可以转换为矩形
3. 矩形可以通过剪切和拼接变成正方形
4. 因此，两个等面积多边形可以通过"正方形"作为中间形状互相转换

1.3 算法思路

核心流程：

S → 三角形集合 → 矩形条集合 → 大正方形 → 新矩形条集合 → T的三角形集合 → T

步骤详解：

1. 三角剖分：将 $S$ 和 $T$ 分别剖分成三角形
2. 三角形→矩形：将 $S$ 的每个三角形转换为等面积矩形
3. 矩形拼接：将所有矩形条拼接成边长为 $\sqrt{\text{area}}$ 的正方形
4. 重新分割：按照 $T$ 的三角形面积，将正方形分割成新的矩形条
5. 矩形→三角形：将每个矩形条转换为 $T$ 的对应三角形
6. 最终拼接：将所有三角形拼接成 $T$

二、数学推导

2.1 三角形到矩形的转换

定理1（三角形等面积矩形转换）：

任意三角形可以剪切重组为等面积矩形。

构造方法：

设三角形三个顶点为 $(0, 0)$、$(a, 0)$、$(p, h)$（已经移动到"地面"），面积为 $S = \frac{ah}{2}$。

目标矩形：宽 $a$，高 $\frac{h}{2}$，面积 $S = a \cdot \frac{h}{2}$。

剪切方案：

1. 在高度 $\frac{h}{2}$ 处作水平线，将三角形分成三部分
2. 左侧梯形保持不动
3. 右上角小三角形旋转180°移到右侧
4. 左上角小三角形旋转180°移到左侧

数学证明：

设中线与三角形两边的交点为：

• 左交点：$P_L = (\frac{p}{2}, \frac{h}{2})$
• 中间点：$P_M = (p, \frac{h}{2})$
• 右交点：$P_R = (\frac{p+a}{2}, \frac{h}{2})$

分割后的三部分：

• 梯形：$(0,0)$、$(a,0)$、$P_R$、$P_L$
• 右上三角形：$P_M$、$P_R$、$(p,h)$
• 左上三角形：$P_L$、$P_M$、$(p,h)$

拼接后形成矩形：$(0,0)$、$(a,0)$、$(a,\frac{h}{2})$、$(0,\frac{h}{2})$

2.2 矩形到正方形的转换

定理2（矩形等面积正方形转换）：

任意矩形可以通过有限次剪切和拼接转换为等面积正方形。

算法策略：

设当前矩形尺寸为 $x \times y$，目标正方形边长为 $s = \sqrt{xy}$。

步骤1：将矩形调整到"近似正方形"

• 如果 $x > 2y$：横切成两半，纵向拼接，得到 $\frac{x}{2} \times 2y$
• 如果 $y > 2x$：纵切成两半，横向拼接，得到 $2x \times \frac{y}{2}$
• 重复直到 $\frac{x}{2} \le y \le 2x$

步骤2：精确调整到目标尺寸

使用 transform_rect 函数进行精细调整。

数学分析：

当 $x > s$ 且 $y < s$ 时（面积守恒：$xy = s^2$）：

剪切方案：

原矩形 (0,0)-(x,y) 分成三部分：
1. 五边形：(0,0)-(s,0)-(s,s-y)-(x-s,y)-(0,y)
2. 三角形：(s,0)-(x,0)-(s,s-y)
3. 三角形：(x-s,y)-(x,0)-(x,y)

移动后拼成：$(0,0)-(s,s)$ 的正方形。

2.3 正确性证明

引理1（面积守恒）：每次剪切和拼接操作保持总面积不变。

证明：显然，剪切只是划分，拼接只是重新组合，不改变总面积。

引理2（有限步骤）：算法在有限步内终止。

证明：

• 三角剖分：$O(n)$ 个三角形
• 每个三角形到矩形：$O(1)$ 次操作
• 矩形到正方形：每次操作使得长宽比减半，$O(\log(\frac{x}{y}))$ 次
• 总操作数：$O(n \log(\frac{x}{y}))$

定理3（算法正确性）：该算法能将任意等面积多边形 $S$ 转换为 $T$。

证明：

1. 三角剖分后，$S$ 和 $T$ 都被分解为三角形
2. 每个三角形都能转换为矩形（引理1）
3. 所有矩形拼接成正方形（引理2）
4. 正方形可以重新分割并转换回 $T$ 的三角形
5. 所有操作保持面积守恒
6. 因此算法正确 ✓

三、代码模块详解

模块1：基础几何结构

struct Point {
    double x, y;
    Point(double _x = 0, double _y = 0) {
        x = _x, y = _y;
    }
    Point operator - (const Point &a)const {
        return Point(x - a.x, y - a.y);
    }
    double operator ^ (const Point &a)const {
        return x * a.y - y * a.x;  // 叉积
    }
};

叉积的几何意义：

$$\vec{a} \times \vec{b} = |a||b|\sin\theta$$

对于二维向量：$(x_1, y_1) \times (x_2, y_2) = x_1y_2 - y_1x_2$

应用：

• 计算三角形面积：$S = \frac{|\vec{AB} \times \vec{AC}|}{2}$
• 判断点在线段的哪一侧
• 判断线段是否相交

模块2：多边形结构

struct Polygon {
    int n;
    vector<Point> nds;
    
    void doshift(Point x) {
        for (auto &i : nds)
            i = i + x;
    }
};

功能：

• 存储多边形的顶点
• 提供平移操作
• 输入输出接口

模块3：线段相交判断

bool isinter(Point l1, Point r1, Point l2, Point r2) {
    if (sgn((l2 - l1) ^ (r1 - l1))*sgn((r2 - l1) ^ (r1 - l1)) >= 0)
        return false;
    if (sgn((l1 - l2) ^ (r2 - l2))*sgn((r1 - l2) ^ (r2 - l2)) >= 0)
        return false;
    return true;
}

算法原理：跨立实验

线段 $L_1L_2$ 与 $R_1R_2$ 相交当且仅当：

• $L_1$ 和 $L_2$ 在线段 $R_1R_2$ 的两侧
• $R_1$ 和 $R_2$ 在线段 $L_1L_2$ 的两侧

数学判断：

使用叉积判断点在直线的哪一侧：

$$\text{sgn}(\vec{R_1L_1} \times \vec{R_1R_2}) \cdot \text{sgn}(\vec{R_1L_2} \times \vec{R_1R_2}) < 0 $$

模块4：三角剖分

vector<Polygon> Split(Polygon v) {
    if (v.n == 3)
        return vector<Polygon> {v};
    
    for (int i = 0; i < v.n; i++)
        for (int j = i + 2; j < v.n; j++)
            if (i || j + 1 < v.n) {
                // 检查对角线 v[i]-v[j] 是否合法
                bool ok = true;
                for (int k = 0; k < v.n; k++) {
                    if (/* 跳过相邻边 */)
                        continue;
                    if (isinter(v[k], v[(k + 1) % v.n], v[i], v[j])) {
                        ok = false;
                        break;
                    }
                }
                
                if (!ok) continue;
                
                // 检查对角线是否在多边形内部（射线法）
                Point mid = (v[i] + v[j]) / 2;
                int num = 0;
                for (int k = 0; k < v.n; k++)
                    if (isinter(v[k], v[(k + 1) % v.n], mid, 无穷远点))
                        num ^= 1;
                
                if (!num) continue;
                
                // 递归剖分两个子多边形
                auto sl = Split(左子多边形);
                auto sr = Split(右子多边形);
                return 合并(sl, sr);
            }
}

算法思路：

1. 枚举所有可能的对角线
2. 检查对角线是否与多边形边相交
3. 使用射线法判断对角线中点是否在多边形内部
4. 沿着合法对角线将多边形分成两部分
5. 递归剖分两个子多边形

射线法：

从点 $P$ 发出一条射线，统计与多边形边的交点数：

• 奇数：点在内部
• 偶数：点在外部

时间复杂度：$O(n^3)$（每次找对角线 $O(n^2)$，递归深度 $O(n)$）

模块5：三角形标准化

Polygon move_to_ground(Polygon px) {
    // 找到最长边
    pair<double, int> mxlen = make_pair(-114, 0);
    for (int i = 0; i < 3; i++)
        mxlen = max(mxlen, make_pair((px[(i + 1) % 3] - px[i]).len(), i));
    
    int i = mxlen.S;
    double len = (px[(i + 1) % 3] - px[i]).dis();
    double ty = fabs((px[1] - px[0]) ^ (px[2] - px[0])) / len;  // 高
    double tx = sqrt((px[(i + 2) % 3] - px[i]).len() - ty * ty);  // 底边投影
    
    vector<Point> cur(3);
    cur[i] = Point(0, 0);
    cur[(i + 1) % 3] = Point(len, 0);
    cur[(i + 2) % 3] = Point(tx, ty);
    return Polygon(cur);
}

功能：将三角形标准化，使得最长边在 $x$ 轴上。

数学原理：

设三角形三个顶点为 $A, B, C$，最长边为 $AB$。

1. 将 $A$ 移动到原点：$A' = (0, 0)$
2. 将 $B$ 移动到 $x$ 轴：$B' = (|AB|, 0)$
3. 计算 $C$ 的新坐标：
   • 高度：$h = \frac{2S}{|AB|} = \frac{|\vec{AB} \times \vec{AC}|}{|AB|}$
   • 水平距离：$d = \sqrt{|AC|^2 - h^2}$
   • $C' = (d, h)$

模块6：三角形到矩形转换

int tri_to_rect(int x, Polygon to) {
    // 标准化三角形
    auto t0 = move_to_ground(p[x]);
    p[x] = t0;
    x = Merge(vector<int> {x}, t0);
    
    // 找到左下角顶点
    int id = 0;
    for (int i = 0; i < 3; i++)
        if (make_pair(p[x][i].x, p[x][i].y) < make_pair(p[x][id].x, p[x][id].y))
            id = i;
    
    double pos = p[x][(id + 2) % 3].x, hei = p[x][(id + 2) % 3].y;
    
    // 计算分割点
    Point pl = Point(pos / 2.0, hei / 2.0);  // 左中点
    Point pmid = Point(pos, hei / 2.0);       // 中间点
    Point pr = Point((pos + p[x][(id + 1) % 3].x) / 2.0, hei / 2.0);  // 右中点
    
    // 分成三部分：梯形 + 两个三角形
    Polygon p0 = 梯形;
    Polygon p1 = 右上三角形;
    Polygon p2 = 左上三角形;
    
    vector<int> v = Cut(x, {p0, p1, p2});
    
    // 旋转并拼接成矩形
    p[v[1]] = 旋转后的右三角形;
    p[v[2]] = 旋转后的左三角形;
    x = Merge(v, 矩形);
    
    return rect_to_rect(x, to);  // 调整矩形尺寸
}

几何变换：

原三角形（标准化后）：

• 底边：$(0, 0)$ 到 $(a, 0)$
• 顶点：$(p, h)$

在 $y = \frac{h}{2}$ 处水平切割，得到：

1. 梯形：保持不动
2. 右上小三角形：旋转180°，移动到右侧
3. 左上小三角形：旋转180°，移动到左侧

最终矩形：$(0, 0) - (a, \frac{h}{2})$

模块7：矩形尺寸调整

int transform_rect(int x, double sx, double sy, double tx, double ty) {
    if (fabs(sx - tx) < eps && fabs(sy - ty) < eps)
        return x;
    
    if (sx > tx) {
        // 当前宽度大于目标宽度
        Point p0(tx, 0), p1(tx, ty - sy), p2(sx - tx, sy);
        Polygon v0 = 五边形（左侧主体）;
        Polygon v1 = 右上三角形;
        Polygon v2 = 右下三角形;
        
        auto v = Cut(x, {v0, v1, v2});
        
        p[v[1]].doshift(Point(-tx, sy));      // 右上移到左上
        p[v[2]].doshift(Point(tx - sx, ty - sy));  // 右下移到上方
        
        return Merge(v, make_rect(0, 0, tx, ty));
    }
    
    // 对称情况：sx < tx
    // ...
}

数学推导：

设当前矩形 $sx \times sy$，目标矩形 $tx \times ty$，满足 $sx \cdot sy = tx \cdot ty$（面积守恒）。

情况1：$sx > tx$（必然 $sy < ty$）

剪切策略：

原矩形分成三部分：
1. 五边形：宽度tx，包含大部分面积
2. 右上三角形：面积 = (sx-tx)(ty-sy)/2
3. 右下三角形：面积 = (sx-tx)(ty-sy)/2

移动后：

• 右上三角形移到左上角
• 右下三角形移到顶部
• 拼成 $tx \times ty$ 的矩形

面积验证：

$$\begin{aligned} \text{五边形面积} &= tx \cdot ty - \frac{(tx-sx)(ty-sy)}{2} \cdot 2 \\ &= tx \cdot ty - (tx-sx)(ty-sy) \\ &= sx \cdot sy \quad (\text{因为 } sx \cdot sy = tx \cdot ty) \end{aligned} $$

模块8：矩形到矩形转换（完整流程）

int rect_to_rect(int x, Polygon to) {
    // 步骤1：移动到原点
    if (fabs(p[x][0].x) > eps || fabs(p[x][0].y) > eps) {
        p[x].doshift(-p[x][0]);
        x = Merge(vector<int> {x}, p[x]);
    }
    
    sx = p[x][2].x, sy = p[x][2].y;
    tx = to[2].x - to[0].x, ty = to[2].y - to[0].y;
    
    // 步骤2：调整到"近似正方形"
    while (sx > sy * 2.0 + eps) {
        // 横向切半，纵向拼接
        Polygon p0 = make_rect(0, 0, sx / 2.0, sy);
        Polygon p1 = make_rect(sx / 2.0, 0, sx, sy);
        auto v = Cut(x, {p0, p1});
        p[v[1]].doshift(Point(-sx / 2.0, sy));
        x = Merge(v, make_rect(0, 0, sx / 2.0, sy * 2.0));
        sx /= 2.0, sy *= 2.0;
    }
    
    while (sy > sx * 2.0 + eps) {
        // 纵向切半，横向拼接（对称）
        // ...
        sy /= 2.0, sx *= 2.0;
    }
    
    // 步骤3：记录目标路径
    vector<pair<double, double>> pth;
    while (tx > ty * 2.0 + eps)
        pth.push_back({tx, ty}), tx /= 2.0, ty *= 2.0;
    while (ty > tx * 2.0 + eps)
        pth.push_back({tx, ty}), ty /= 2.0, tx *= 2.0;
    
    // 步骤4：精确调整
    x = transform_rect(x, sx, sy, tx, ty);
    
    // 步骤5：反向展开到目标尺寸
    for (int i = pth.size() - 1; i >= 0; i--) {
        // 逆向操作
        // ...
    }
    
    // 步骤6：移动到目标位置
    if (fabs(to[0].x) > eps || fabs(to[0].y) > eps) {
        p[x] = to;
        x = Merge(vector<int> {x}, to);
    }
    
    return x;
}

算法分析：

阶段1：收缩到"近似正方形"

• 保持长宽比在 $[\frac{1}{2}, 2]$ 之间
• 每次操作将长边减半

阶段2：精确调整

• 使用 transform_rect 一步到位

阶段3：展开到目标尺寸

• 逆向操作，从"近似"展开到精确目标

复杂度：每次减半，操作次数 $O(\log \frac{\max(sx,sy)}{\min(sx,sy)})$

模块9：主算法

int main() {
    ps.getinput(), pt.getinput();
    p[0] = ps;
    cnt = 1;
    
    // 步骤1：三角剖分
    auto mks = Split(ps);
    auto mkt = Split(pt);
    
    // 步骤2：计算总面积和正方形边长
    double area = 0;
    for (auto &x : mks)
        area += fabs((x[1] - x[0]) ^ (x[2] - x[0]));
    area /= 2.0;
    double len = sqrt(area);
    
    // 步骤3：将S的三角形转换为矩形条
    double pre = 0;
    vector<int> ids = Cut(0, mks), idt;
    for (int i = 0; i < ids.size(); i++) {
        auto x = mks[i];
        double s = fabs((x[1] - x[0]) ^ (x[2] - x[0])) / 2.0;
        s /= len;  // 矩形宽度
        idt.push_back(tri_to_rect(ids[i], make_rect(pre, 0, pre + s, len)));
        pre += s;
    }
    
    // 步骤4：拼接成正方形
    int x = Merge(idt, make_rect(0, 0, len, len));
    
    // 步骤5：分割成T的矩形条
    vector<Polygon> cur;
    pre = 0;
    for (auto &x : mkt) {
        double s = fabs((x[1] - x[0]) ^ (x[2] - x[0])) / 2.0;
        s /= len;
        cur.push_back(make_rect(pre, 0, pre + s, len));
        pre += s;
    }
    idt = Cut(x, cur);
    
    // 步骤6：将矩形条转换为T的三角形
    for (int i = 0; i < idt.size(); i++)
        idt[i] = rect_to_tri(idt[i], mkt[i]);
    
    // 步骤7：拼接成T
    x = Merge(idt, pt);
    
    return 0;
}

算法流程图：

输入：S, T
  ↓
三角剖分：S → {T₁, T₂, ..., Tₙ}
  ↓
转矩形：Tᵢ → Rᵢ (宽 = Sᵢ/len, 高 = len)
  ↓
拼正方形：[R₁|R₂|...|Rₙ] → □ (边长 = len)
  ↓
重新分割：□ → [R'₁|R'₂|...|R'ₘ] (按T的三角形面积)
  ↓
转三角形：R'ⱼ → T'ⱼ
  ↓
拼接：{T'₁, T'₂, ..., T'ₘ} → T

四、复杂度分析

4.1 时间复杂度

三角剖分：$O(n^3)$（暴力枚举对角线）

三角形到矩形：$O(1)$ 次剪切和拼接，每个三角形 $O(1)$

矩形到正方形：

• 收缩阶段：$O(\log \frac{x}{y})$ 次操作
• 精确调整：$O(1)$ 次
• 展开阶段：$O(\log \frac{x}{y})$ 次

总时间复杂度：$O(n^3 + n \log \frac{x}{y})$

4.2 操作次数

剪切次数：

• 三角剖分：$1$ 次（分成 $n$ 个三角形）
• 每个三角形到矩形：$1$ 次
• 矩形到正方形：$O(n \log \frac{x}{y})$ 次
• 正方形到矩形：$1$ 次
• 矩形到三角形：$O(n)$ 次

总操作数：$O(n \log \frac{x}{y})$，远小于题目限制 $2000$

4.3 空间复杂度

形状数量：每次操作最多产生常数个新形状，总数 $O(n \log \frac{x}{y})$

顶点总数：每个形状最多 $100$ 个点（题目限制），实际使用远小于此

六、总结

6.1 核心思想

本题采用的中间形状转换思想：

1. 标准化：将所有多边形转换为三角形
2. 中间形状：通过矩形和正方形作为"桥梁"
3. 对称构造：先分解后组合，保持面积守恒

6.2 数学基础

Wallace-Bolyai-Gerwien 定理的构造性证明：

通过本题的算法，我们实际上给出了该定理的一个构造性证明方法：

1. 任意多边形可剖分为三角形
2. 三角形可转换为矩形
3. 矩形可组合成正方形
4. 因此任意等面积多边形可互相转换