UVa 11509 Touring Robot

本文研究了游览机器人在平面路径上的旋转圈数问题。通过分析机器人运动轨迹形成的闭合多边形，发现其旋转圈数等于多边形外角之和除以2π。算法核心是计算相邻向量间的逆时针旋转角度，并累加后除以2π取整。对于N个点的路径，时间复杂度为O(N)，空间复杂度为O(N)。使用向量叉积和点积计算旋转角度，并处理浮点数精度问题。最终将几何问题转化为计算多边形旋转数的数学问题，给出了高效解决方案。

寂静山林

665人浏览 · 2026-01-25 08:59:09

寂静山林 · 2026-01-25 08:59:09 发布

题目描述

$TRobots\texttt{TRobots}$ 公司制造并维护一种名为“游览机器人”的特殊机器人。这种机器人在笛卡尔平面中按照预定路径移动并执行任务。一个任务由至少两个点构成，机器人必须按照以下规则依次访问这些点：

机器人在第一个点处开始，并面向第二个点；
机器人沿着当前面向的方向移动；
当到达序列中的一个点时，机器人会逆时针旋转一个角度 $α\alpha$ （ $\leq \alpha < 2\pi$ ），直到面向序列中的下一个点（注意：序列是循环的，即最后一个点的下一个点是第一个点）；
机器人在返回第一个点后结束任务，此时它面向第二个点。

由于机器人在整个游览过程中会不断地旋转，最终它会完成整数圈旋转。 $TRobots\texttt{TRobots}$ 公司认为这个圈数很重要，因为它决定了机器人何时需要进行维护。你的任务是：给定一个游览任务（即一系列点的坐标），计算机器人在完成该任务时总共旋转了多少圈。

输入格式

输入包含多个测试用例。每个测试用例的格式如下：

第一行：一个整数 $N$ （ $1 < N < 1000$ ），表示游览中需要访问的点的数量。
接下来的 $N$ 行：每行包含两个整数 $x$ 和 $y$ （ $−106≤x,y≤106-10^{6} \leq x, y \leq 10^{6}$ ），表示一个点的坐标。保证相邻的点（包括最后一个点和第一个点）不相同。

输入以 $N = 0$ 结束。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示机器人完成该游览任务所旋转的圈数。

样例输入

样例输出

题目分析

这道题的核心在于理解机器人的运动方式，并将其转化为几何问题。

1. 运动过程分析

机器人从第一个点出发，沿着当前面向的方向移动到下一个点。到达一个点后，它会逆时针旋转，直到面向下一个点，然后继续移动。这个过程会一直持续，直到它返回起点。

如果我们把机器人访问的所有点按顺序连起来，就得到了一个闭合多边形。机器人在每个顶点处都需要旋转一个角度，这个角度就是多边形在该顶点处的外角。

2. 数学原理

对于一个简单的闭合多边形（不自交），其外角之和总是 $360∘360^\circ$ （即 $2π2\pi$ 弧度）。然而，如果多边形是复杂的（例如自交、有凹陷等），那么外角之和就不再是 $2π2\pi$ ，而是 $2π×k2\pi \times k$ ，其中 $k$ 是一个整数，称为多边形的旋转数（ $number\texttt{winding number}$ ）或圈数。

旋转数 $k$ 表示：当我们绕着多边形走一圈时，我们的方向总共旋转了多少个完整的 $360∘360^\circ$ 。顺时针旋转会减少 $k$ ，逆时针旋转会增加 $k$ 。在本题中，机器人总是逆时针旋转，所以 $k$ 一定是非负整数。

3. 问题转化

因此，问题转化为：给定一个闭合多边形的顶点坐标（按访问顺序），计算这个多边形的旋转数。

具体来说，我们需要：

对于每个顶点 $P_i$ ，计算从 $P_{i-1}$ 到 $P_i$ 的向量 $u⃗\vec{u}$ ，和从 $P_i$ 到 $P_{i+1}$ 的向量 $v⃗\vec{v}$ 。
计算从 $u⃗\vec{u}$ 逆时针旋转到 $v⃗\vec{v}$ 的角度 $αi\alpha_i$ （ $\leq \alpha_i < 2\pi$ ）。
将所有 $αi\alpha_i$ 累加，得到总旋转角度 $\sum \alpha_i$ 。
计算圈数 $\frac{T}{2\pi}$ ，并四舍五入到最近的整数（由于浮点数精度问题，需要处理微小误差）。

4. 角度计算方法

设 $u⃗=(ux,uy)\vec{u} = (u_x, u_y)$ ， $v⃗=(vx,vy)\vec{v} = (v_x, v_y)$ 。我们可以通过向量叉积和点积来计算旋转角度：

叉积： $u⃗×v⃗=uxvy−uyvx\vec{u} \times \vec{v} = u_x v_y - u_y v_x$ 。它的符号表示旋转方向：正数表示逆时针旋转，负数表示顺时针旋转。
点积： $u⃗⋅v⃗=uxvx+uyvy\vec{u} \cdot \vec{v} = u_x v_x + u_y v_y$ 。它用于计算两个向量夹角的余弦值。

使用 $atan2\texttt{atan2}$ 函数可以方便地计算两个向量之间的夹角（以弧度为单位）：
$\theta = \texttt{atan2}(\vec{u} \times \vec{v}, \ \vec{u} \cdot \vec{v})$
$atan2\texttt{atan2}$ 返回值的范围是 $[−π,π][-\pi, \pi]$ 。由于我们需要的是逆时针旋转的角度（ $0$ 到 $2π2\pi$ ），因此当 $θ<0\theta < 0$ 时，需要加上 $2π2\pi$ 。

5. 算法步骤

读入点的数量 $N$ ，如果 $N = 0$ 则结束程序。
读入 $N$ 个点的坐标，存储到数组中。
为了方便处理循环，将第一个点复制到数组末尾，这样 $P_{N} = P_0$ 。
对于每个顶点 $P_i$ （ $i = 0$ 到 $N - 1$ ）：
- 计算向量 $u⃗=Pi−1Pi\vec{u} = P_{i-1}P_i$ 和 $v⃗=PiPi+1\vec{v} = P_i P_{i+1}$ 。注意当 $i = 0$ 时， $P_{i-1}$ 应该是 $P_{N-1}$ （即原始多边形的最后一个点）。
- 使用上述方法计算从 $u⃗\vec{u}$ 到 $v⃗\vec{v}$ 的逆时针旋转角度 $αi\alpha_i$ 。
- 累加 $αi\alpha_i$ 。
计算总旋转角度 $T$ ，然后计算圈数 $\texttt{round}(T / (2\pi))$ 。
输出 $k$ 。

6. 时间复杂度

该算法只需遍历所有顶点一次，每次计算都是常数时间，因此时间复杂度为 $O (N)$ ，空间复杂度为 $O (N)$ 。由于 $N < 1000$ ，该算法效率很高。

7. 边界情况与精度处理

浮点数精度：由于使用 $atan2\texttt{atan2}$ 和除法，结果可能会有微小误差。因此，在计算圈数时，我们使用 $round\texttt{round}$ 函数进行四舍五入，而不是直接截断。
坐标范围：坐标值的绝对值可达 $10^6$ ，在计算叉积和点积时，可能会超过 $32$ 位整数的范围。因此，我们使用 double 类型进行计算，避免溢出。

代码实现

// Touring Robot
// UVa ID: 11509
// Verdict: Accepted
// Submission Date: 2026-01-07
// UVa Run Time: 0.010s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

const double PI = acos(-1.0);
const double EPS = 1e-9;

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}
};

// 计算两点之间的向量
Point vectorBetween(const Point& a, const Point& b) {
    return Point(b.x - a.x, b.y - a.y);
}

// 计算从向量u旋转到向量v的逆时针角度（0到2π）
double rotationAngle(const Point& u, const Point& v) {
    double cross = u.x * v.y - u.y * v.x;  // 叉积
    double dot = u.x * v.x + u.y * v.y;    // 点积
    // 使用atan2计算角度，确保结果在[0, 2π)范围内
    double angle = atan2(cross, dot);
    if (angle < 0) angle += 2 * PI;
    return angle;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n != 0) {
        vector<Point> points(n);
        for (int i = 0; i < n; i++) scanf("%d %d", &points[i].x, &points[i].y);
        // 多边形闭合，添加第一个点作为最后一个点以便计算
        points.push_back(points[0]);
        double totalAngle = 0.0;
        for (int i = 0; i < n; i++) {
            // 当前点
            Point current = points[i];
            // 前一个点
            Point prev = (i == 0) ? points[n - 1] : points[i - 1];
            // 下一个点
            Point next = points[i + 1];
            // 计算两个向量：从前一点到当前点，从当前点到下一点
            Point vec1 = vectorBetween(prev, current);
            Point vec2 = vectorBetween(current, next);
            // 累加旋转角度
            totalAngle += rotationAngle(vec1, vec2);
        }
        // 总旋转角度除以2π得到圈数，四舍五入到最接近的整数
        int turns = round(totalAngle / (2 * PI));
        printf("%d\n", turns);
    }
    return 0;
}