题解：多边形顶点坐标重构

题目理解

这道题目要求我们根据给定的等腰三角形顶点和角度信息，重构原始多边形的顶点坐标。具体来说：

1. 给定一个顺时针排列的$n$边形，每条边外侧构造了一个等腰三角形
2. 已知这些等腰三角形的顶点$M_i$坐标和顶角$\alpha_i$
3. 需要还原原始多边形顶点$A_i$的坐标
4. 题目保证任何非空子集的角度和不能被$360^\circ$整除（确保解的唯一性）

算法思路

1. 几何构造：利用等腰三角形的性质，通过$M_i$和$\alpha_i$确定原始边$A_iA_{i+1}$的位置
2. 向量旋转：将边向量旋转$\frac{\alpha_i}{2}$角度得到两条方向线
3. 直线交点：计算两条方向线的交点确定多边形顶点
4. 坐标调整：可能需要整体平移、旋转或缩放来匹配给定条件

数学原理

1. 对于每个等腰三角形$M_i$：
   • 两条腰与底边的夹角均为$\frac{\alpha_i}{2}$
   • 原始多边形的边$A_iA_{i+1}$是等腰三角形的底边
2. 通过向量旋转公式计算方向向量：$$\mathbf{v}_{\text{rot}} = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix} \mathbf{v} $$
3. 两条方向线的交点即为原始多边形顶点

代码实现与注释

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>  // 用于控制输出格式

using namespace std;

// 定义二维点结构体，包含x和y坐标
struct Point {
    double x, y;
    Point() : x(0), y(0) {}  // 默认构造函数，初始化为(0,0)
    Point(double x, double y) : x(x), y(y) {}  // 带参构造函数
};

// 运算符重载：点加法
Point operator+(const Point& a, const Point& b) {
    return Point(a.x + b.x, a.y + b.y);
}

// 运算符重载：点减法
Point operator-(const Point& a, const Point& b) {
    return Point(a.x - b.x, a.y - b.y);
}

// 运算符重载：点乘标量
Point operator*(const Point& a, double k) {
    return Point(a.x * k, a.y * k);
}

// 计算点积（内积）
double dot(const Point& a, const Point& b) {
    return a.x * b.x + a.y * b.y;
}

// 计算叉积（外积）
double cross(const Point& a, const Point& b) {
    return a.x * b.y - a.y * b.x;
}

// 计算向量长度（模）
double norm(const Point& a) {
    return sqrt(dot(a, a));
}

// 向量旋转函数（角度制输入）
Point rotate(const Point& p, double angle) {
    double rad = angle * M_PI / 180.0;  // 角度转弧度
    double c = cos(rad), s = sin(rad);
    return Point(p.x * c - p.y * s, p.x * s + p.y * c);
}

// 多边形重构主函数
vector<Point> reconstruct_polygon(int n, const vector<Point>& M, const vector<double>& alpha) {
    vector<Point> A(n);  // 存储重构的多边形顶点
    A[0] = Point(0, 0);  // 初始化第一个顶点为原点
    
    for (int i = 0; i < n; ++i) {
        int next = (i + 1) % n;  // 下一个顶点索引（循环处理）
        Point vec = M[next] - M[i];  // 计算M_i到M_{i+1}的向量
        
        // 将向量旋转±α_i/2角度得到两条方向线
        double angle = alpha[i] / 2;
        Point dir1 = rotate(vec, angle);  // 正向旋转
        Point dir2 = rotate(vec, -angle); // 反向旋转
        
        // 单位化方向向量
        dir1 = dir1 * (1.0 / norm(dir1));
        dir2 = dir2 * (1.0 / norm(dir2));
        
        // 计算两条方向线的交点（解线性方程组）
        double det = dir1.x * dir2.y - dir1.y * dir2.x;  // 行列式
        
        if (fabs(det) < 1e-8) {  // 处理平行情况（理论上不会出现）
            A[next] = A[i] + vec;
        } else {
            Point diff = M[next] - M[i];
            // 使用克莱姆法则解方程
            double t = (diff.x * dir2.y - diff.y * dir2.x) / det;
            A[next] = M[i] + dir1 * t;  // 计算交点作为多边形顶点
        }
    }
    
    return A;
}

int main() {
    int n;
    cin >> n;  // 读取多边形边数
    
    vector<Point> M(n);  // 存储等腰三角形顶点坐标
    for (int i = 0; i < n; ++i) {
        cin >> M[i].x >> M[i].y;  // 读取M_i坐标
    }
    
    vector<double> alpha(n);  // 存储顶角角度
    for (int i = 0; i < n; ++i) {
        cin >> alpha[i];  // 读取角度值
    }
    
    // 重构多边形顶点
    vector<Point> A = reconstruct_polygon(n, M, alpha);
    
    // 设置输出格式（保留两位小数）
    cout << fixed << setprecision(2);
    for (const Point& p : A) {
        cout << p.x << " " << p.y << endl;  // 输出顶点坐标
    }
    
    return 0;
}

复杂度分析

1. 时间复杂度：$O(n)$
   • 单次循环处理每个边和角度
   • 每个步骤都是常数时间操作
2. 空间复杂度：$O(n)$
   • 存储顶点坐标和角度值

示例说明

1. 对于每个等腰三角形顶点$M_i$和顶角$\alpha_i$：
   • 计算两条与底边成$\frac{\alpha_i}{2}$夹角的方向线
   • 这两条方向线的交点即为原始多边形顶点$A_{i+1}$
2. 通过向量旋转和线性方程组求解，可以高效地重构整个多边形
3. 最终输出的顶点坐标保留了两位小数精度