题解

题意分析

题目描述了一个地鼠逃生的问题：

• 地鼠和狗分别位于平面上的固定坐标点。
• 地鼠会选择某个地洞并以恒定速度直线逃向该地洞。
• 狗的速度是地鼠的两倍，会直接冲向地鼠选择的地洞。
• 需要判断是否存在一个地洞，使得地鼠能在狗之前到达（即地鼠到地洞的距离$dist_g$满足$2 \times dist_g < dist_d$，其中$dist_d$是狗到地洞的距离）。

解题思路

1. 距离计算：对于每个地洞，计算地鼠和狗到该地洞的欧几里得距离。
2. 比较条件：检查是否存在地洞满足$2 \times dist_g < dist_d$。
3. 输出结果：如果存在满足条件的地洞，输出第一个符合条件的；否则输出无法逃脱。

实现步骤

1. 输入处理：读取地鼠和狗的坐标，以及所有地洞的坐标。
2. 遍历地洞：对每个地洞计算地鼠和狗到它的距离。
3. 条件判断：检查是否满足逃生条件。
4. 输出结果：根据判断结果输出相应信息。

代码注释

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

// 定义点的结构体，存储x和y坐标
struct Point {
    double x, y;
};

// 计算两点之间的欧几里得距离
double distance(Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main() {
    Point gopher, dog; // 定义地鼠和狗的坐标点
    cin >> gopher.x >> gopher.y >> dog.x >> dog.y; // 读取地鼠和狗的坐标

    vector<Point> holes; // 存储所有地洞的坐标
    Point hole;
    while (cin >> hole.x >> hole.y) { // 循环读取每个地洞的坐标
        holes.push_back(hole);
    }

    // 遍历所有地洞
    for (const auto& h : holes) {
        double dist_gopher = distance(gopher, h); // 计算地鼠到当前地洞的距离
        double dist_dog = distance(dog, h);       // 计算狗到当前地洞的距离

        // 判断地鼠是否能逃生：地鼠到达时间是否小于狗的一半
        if (2 * dist_gopher < dist_dog) {
            cout << "The gopher can escape through the hole at (";
            cout << fixed << setprecision(3) << h.x << "," << h.y << ")." << endl;
            return 0; // 找到第一个满足条件的地洞后立即结束程序
        }
    }

    // 没有找到满足条件的地洞
    cout << "The gopher cannot escape." << endl;
    return 0;
}

复杂度分析

• 时间复杂度：假设地洞数量为$n$，每个地洞的距离计算时间为$O(1)$，总时间复杂度为$O(n)$。
• 空间复杂度：使用一个向量存储所有地洞坐标，空间复杂度为$O(n)$。