UVA10310 题解

hj23308 · 2022-11-23 10:06:15 · 题解

题目传送门

1. 题意

多组数据。
有一只狗和一只地鼠，地鼠有 n 个洞。给出狗和地鼠初始坐标与 n 个洞的坐标。
狗的速度是地鼠的两倍，问地鼠能否安全逃到一个洞中，若有多解则输出编号靠前的一个。

2. 分析

读入后按顺序枚举每个洞，通过勾股定理计算分别到狗和地鼠的距离，记作 s_1, s_2。
若 2\cdot{s}_2\le{s}_1，那么地鼠能安全逃脱，输出答案。
时空复杂度 O(n)。

3. 代码

注意计算距离时不要使用开方，否则会发生精度丢失，可以直接比较。

#include <bits/stdc++.h>

using namespace std;

class point {
private:
    double x, y;
public:
    void read() { cin >> x >> y; }

    void print() { 
        cout << fixed << setprecision(3) << '(' << x << ',' << y << ')';
    }

    double dist(point& rhs) {
        double dx = rhs.x - x, dy = rhs.y - y;
        return dx * dx + dy * dy;
    }
};

point p[1005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    while (cin >> n) {
        point gopher, dog;
        gopher.read(), dog.read();
        for (int i = 1; i <= n; i++)
            p[i].read();

        bool ans = 0;
        for (int i = 1; i <= n; i++)
            if (gopher.dist(p[i]) * 4.0 <= dog.dist(p[i])) {
                ans = 1;
                cout << "The gopher can escape through the hole at ";
                p[i].print();
                cout << ".\n";
                break;
            }
        if (!ans) cout << "The gopher cannot escape.\n";
    }

    return 0;
}