题意分析

题目背景

本题属于计算几何与物理模拟问题，模拟一个凸多边形木轮从山坡上滚下的运动过程。关键点在于通过几何计算确定木轮最终停止时重心的位置。

核心问题

1. 木轮建模：
   • 由$n$个顶点定义的凸多边形。
   • 给定初始重心位置（保证在内部或边界上）。
2. 山坡建模：
   • 由一系列斜率递减的线段组成，最后一段水平。
   • 每条线段由长度和斜率定义。
3. 运动规则：
   • 木轮绕顶点旋转，每次旋转需使重心$y$坐标减小。
   • 旋转持续到无法找到满足条件的顶点为止。

输入输出

• 输入：
  • 测试用例数$t$。
  • 每个测试用例包含：
    • 木轮顶点数$n$和顶点坐标。
    • 重心初始坐标。
    • 山坡线段参数（长度和斜率）。
    • 第一段线段右端点坐标。
• 输出：木轮最终重心的$x$和$y$坐标（保留3位小数）。

解题思路

1. 几何预处理

1. 山坡线段端点计算：
   • 从第一段线段的右端点出发，根据长度和斜率递推每条线段的左端点。
   • 公式：$$\Delta x = \frac{L}{\sqrt{1 + m^2}}, \quad \Delta y = m \Delta x $$其中$L$为线段长度，$m$为斜率。
2. 初始接触点确定：
   • 遍历所有顶点，找到与山坡线段重合的点（满足$|m(x - x_0) + y_0 - y| \leq 10^{-6}$）。

2. 运动模拟

1. 单一线段情况（水平地面）：
   • 木轮绕顶点旋转，直到重心位于顶点正下方。
   • 旋转角度通过极坐标变换计算：$$\theta = \arctan\left(\frac{\Delta y}{\Delta x}\right), \quad \text{新坐标} = (x_v + r \cos \theta, y_v + r \sin \theta) $$
2. 多线段情况：
   • 每次选择使重心$y$坐标减小的顶点旋转。
   • 计算旋转后与山坡的交点，更新木轮位置和重心。
   • 终止条件：无法找到满足条件的旋转顶点。

3. 关键算法

• 向量旋转：通过极坐标变换更新顶点和重心位置。
• 线段交点计算：解直线与圆的交点方程：$$(x - x_v)^2 + (y - y_v)^2 = r^2, \quad y = m x + b $$

算法实现

代码框架

#include <bits/stdc++.h>
using namespace std;

typedef struct {
    double x, y;
} POINT;

int n;
const double pi = 3.1415926;

POINT p[10], g;

vector<double> vl, vs;

vector<POINT> vp;

inline double dis(POINT p1, POINT p2) {
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

inline double dot(POINT p1, POINT p2, POINT p3) {
    return (p3.x - p2.x) * (p1.x - p2.x) + (p3.y - p2.y) * (p1.y - p2.y);
}

double theta(POINT p2, POINT p1) {
    double dx = p2.x - p1.x, dy = p2.y - p1.y, ret;
    if (dx == 0) {
        if (dy > 0)
            return pi / 2;
        else
            return 1.5 * pi;
    } else {
        ret = atan(dy / dx);
        if (dx > 0) {
            if (dy >= 0)
                return ret;
            else
                return 2 * pi + ret;
        } else
            return pi + ret;
    }
}

int main() {
    int T;

    int i, j, cur_v, cur_l, flag;

    double length, slope, dx, A, B, C, b, dthe, tthe, len;
    POINT tp;

    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);

        for (i = 0; i < n; i++)
            scanf("%lf%lf", &p[i].x, &p[i].y);
        scanf("%lf%lf", &g.x, &g.y);

        vl.clear();
        vs.clear();
        while (1) {
            scanf("%lf%lf", &length, &slope);
            vl.push_back(length);
            vs.push_back(slope);
            if (slope == 0)
                break;
        }

        scanf("%lf%lf", &tp.x, &tp.y);
        vp.clear();
        vp.push_back(tp);
        for (size_t i = 1; i < vs.size(); i++) {
            dx = vl[i - 1] / sqrt(1 + vs[i - 1] * vs[i - 1]);
            tp.x = vp[i - 1].x - dx;
            tp.y = vp[i - 1].y - dx * vs[i - 1];
            vp.push_back(tp);
        }
        for (size_t i = 0; i < vl.size(); i++) {
            for (j = 0; j < n; j++)
                if (fabs(vs[i] * (p[j].x - vp[i].x) + vp[i].y - p[j].y) <= 1e-6) {
                    cur_l = i;
                    cur_v = j;
                    break;
                }
            if (j < n)
                break;
        }

        if (vl.size() == 1) {
            if (g.x > p[cur_v].x)
                flag = 1;
            else if (g.x < p[cur_v].x)
                flag = -1;
            else
                break;
            while (1) {

                tthe = 100;
                for (i = 0; i < n; i++)
                    if (i != cur_v && tthe - flag * theta(p[i], p[cur_v]) > 1e-9) {
                        tthe = flag * theta(p[i], p[cur_v]);
                        j = i;
                    }
                len = dis(p[j], p[cur_v]);
                tp.x = p[cur_v].x + flag * len;
                tp.y = p[cur_v].y;
                dthe = theta(tp, p[cur_v]) - theta(p[j], p[cur_v]);

                for (i = 0; i < n; i++) {
                    len = dis(p[cur_v], p[i]);
                    tthe = dthe + theta(p[i], p[cur_v]);
                    p[i].x = p[cur_v].x + len * cos(tthe);
                    p[i].y = p[cur_v].y + len * sin(tthe);
                }

                len = dis(g, p[cur_v]);
                tthe = dthe + theta(g, p[cur_v]);
                g.x = p[cur_v].x + len * cos(tthe);
                g.y = p[cur_v].y + len * sin(tthe);

                cur_v = j;
                if (flag == 1 && g.x <= p[cur_v].x)
                    break;
                if (flag == -1 && g.x >= p[cur_v].x)
                    break;
            }
        } else {
            while (1) {

                tthe = -100;
                for (i = 0; i < n; i++)
                    if (i != cur_v && tthe - theta(p[i], p[cur_v]) < 1e-9) {
                        tthe = theta(p[i], p[cur_v]);
                        j = i;
                    }

                len = dis(p[j], p[cur_v]);
                for (; cur_l + 1 < static_cast<int>(vl.size()) && dis(p[cur_v], vp[cur_l + 1]) < len;) {
                    cur_l++;
                }

                b = vp[cur_l].y - vs[cur_l] * vp[cur_l].x;
                A = 1 + vs[cur_l] * vs[cur_l];
                B = vs[cur_l] * (b - p[cur_v].y) - p[cur_v].x;
                B *= 2;
                C = p[cur_v].x * p[cur_v].x;
                C += (b - p[cur_v].y) * (b - p[cur_v].y) - len * len;

                tp.x = 2 * C / (-B + sqrt(B * B - 4 * A * C));
                tp.y = vs[cur_l] * tp.x + b;

                dthe = theta(tp, p[cur_v]) - theta(p[j], p[cur_v]);
                for (i = 0; i < n; i++) {
                    len = dis(p[cur_v], p[i]);
                    tthe = dthe + theta(p[i], p[cur_v]);
                    p[i].x = p[cur_v].x + len * cos(tthe);
                    p[i].y = p[cur_v].y + len * sin(tthe);
                }

                len = dis(g, p[cur_v]);
                tthe = dthe + theta(g, p[cur_v]);
                g.x = p[cur_v].x + len * cos(tthe);
                g.y = p[cur_v].y + len * sin(tthe);

                if (g.x >= p[j].x)
                    break;
                cur_v = j;
            }
        }
        printf("%.3lf %.3lf\n", g.x, g.y);
    }
    return 0;
}

关键步骤

1. 输入处理：读取木轮顶点、重心和山坡参数。
2. 山坡建模：计算每条线段的端点坐标。
3. 运动模拟：
   • 单线段：绕顶点旋转至重心垂直下方。
   • 多线段：迭代选择旋转顶点，更新位置直至终止。
4. 输出结果：格式化打印最终重心坐标。

复杂度分析

• 时间：$O(t \cdot n \cdot s)$，其中$s$为山坡线段数。
• 空间：$O(n + s)$，存储顶点和线段信息。