题意分析

题目描述了一个非洲牛羚（$gnu$）在旱季期间，由首领里克（$Rick$）带领前往一个名为"公平视野"（$Fair Sight$，简称$FS$）的更丰美牧场的过程。在这个过程中，牛羚需要在多个小型中间觅食站点停留，以便让牛群恢复体力。题目中给出了以下关键信息和限制条件：

1. 牛羚在两个站点之间的移动距离不能超过 $D$ 个单位。
2. 牛羚始终沿直线行进，只在觅食站点停留并可能改变方向。
3. 牛羚绝不会带领牛群朝远离$FS$的方向移动，最极端的情况也只会选择与$FS$方向垂直的路径。
4. 牛羚总是从所有可能的站点中选择方向最接近$FS$的站点。
5. 牛羚会排除那些需要转向角度超过 $90$ 度的站点。

给定可能的觅食站点地图$FS$的方向以及牛羚群的起点，需要预测牛群的移动路径（直到地图允许的最远位置）。

解题思路

1. 理解问题：首先需要理解题目中给出的限制条件，特别是牛羚选择下一个站点的规则。

2. 数据结构：使用数组或向量来存储站点的坐标，以及一个列表来存储路径。

3. 算法设计：

   • 计算方向向量：首先计算从当前站点到所有其他站点的方向向量。
   • 计算角度：计算每个方向向量与$FS$方向向量之间的夹角，以及与当前方向向量之间的夹角。
   • 筛选站点：根据题目中的限制条件，筛选出符合条件的站点。这包括距离限制、方向限制和转向角度限制。
   • 选择站点：从筛选出的站点中选择一个最接近FS方向的站点作为下一个站点。
   • 更新路径：将选择的站点添加到路径中，并更新当前站点和当前方向向量。
   • 终止条件：当没有符合条件的站点时，终止算法。

4. 实现细节：

   • 使用向量点积来计算两个向量之间的夹角。
   • 使用向量的模长来计算两个站点之间的距离。
   • 使用条件语句来实现筛选和选择站点的逻辑。

标程

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const double EPS = 1e-8;
#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif

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

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 dist(const Point& a, const Point& b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

Point getDirection(const Point& from, const Point& to) {
    return Point(to.x - from.x, to.y - from.y);
}

double getAngle(const Point& a, const Point& b) {
    double dt = dot(a, b);
    double ma = sqrt(a.x * a.x + a.y * a.y);
    double mb = sqrt(b.x * b.x + b.y * b.y);
    if (ma < EPS || mb < EPS) return 0.0;
    double costheta = dt / (ma * mb);
    costheta = max(-1.0, min(1.0, costheta)); // Clamp to avoid numerical errors
    return acos(costheta);
}

int main() {
    double fx, fy;
    int N, S;
    double D;
    while (cin >> fx >> fy >> N >> S >> D) {
        if (N == 0 && S == 0 && D == 0 && fx == 0 && fy == 0) break;
        
        vector<Point> points(N + 1); // 1-based indexing
        for (int i = 1; i <= N; ++i) {
            cin >> points[i].x >> points[i].y;
        }
        
        Point FS(fx, fy);
        vector<int> path;
        vector<bool> visited(N + 1, false);
        int current = S;
        path.push_back(current);
        visited[current] = true;
        Point prevDir(0, 0); // Initial direction is zero (no previous move)
        bool moved;
        
        do {
            moved = false;
            vector<int> candidates;
            // Find all unvisited stations within distance D
            for (int next = 1; next <= N; ++next) {
                if (!visited[next] && next != current) {
                    double d = dist(points[current], points[next]);
                    if (d <= D + EPS) {
                        Point dir = getDirection(points[current], points[next]);
                        // Check if direction is not away from FS
                        if (dot(dir, FS) >= -EPS) {
                            candidates.push_back(next);
                        }
                    }
                }
            }
            
            if (candidates.empty()) break;
            
            // Select the candidate with direction closest to FS
            int bestNext = -1;
            double minAngle = 1e9;
            Point currentPos = points[current];
            for (size_t i = 0; i < candidates.size(); ++i) {
                int next = candidates[i];
                Point dir = getDirection(currentPos, points[next]);
                double angle = getAngle(dir, FS);
                // Check turning angle if not the first move
                if (path.size() > 1) {
                    double turnAngle = getAngle(prevDir, dir);
                    if (turnAngle > M_PI/2 + EPS) {
                        continue; // Skip if turning angle > 90 degrees
                    }
                }
                if (angle < minAngle - EPS) {
                    minAngle = angle;
                    bestNext = next;
                } else if (fabs(angle - minAngle) < EPS) {
                    // If angles are equal, choose the one with smaller number (problem statement ensures no ambiguity)
                    if (next < bestNext || bestNext == -1) {
                        bestNext = next;
                    }
                }
            }
            
            if (bestNext != -1) {
                Point dir = getDirection(points[current], points[bestNext]);
                prevDir = dir;
                current = bestNext;
                path.push_back(current);
                visited[current] = true;
                moved = true;
            }
        } while (moved);
        
        // Output the path
        for (size_t i = 0; i < path.size(); ++i) {
            if (i > 0) cout << " ";
            cout << path[i];
        }
        cout << endl;
    }
    return 0;
}