ZeroJudge H658: 捕魚 (Fishing)

小明是名漁翁,每天都會到開著船到大海去捕魚。捕魚是他熱愛的興趣,為了更有效率的捕獲最多的魚,小明會利用船上的雷達系統來探測週遭的魚群,這樣就可以知道每群與船隻的距離,藉此從最近的地方開始捕獲。
小明希望利用程式快速找到離自己最近的魚群,請你幫幫他。

範例測資

範例輸入範例輸出
輸入第一列有兩個整數 X、Y (0 ≤ X, Y ≤ 500) 表示漁夫的座標位置。第二列有一個整數 N (1 ≤ N ≤ 100) 為魚群的數量。接下來有 N 列,每列有兩個整數 Ai、Bi (0 ≤ Ai, Bi ≤ 500,1 ≤ i ≤ N) 分別表示魚群的中心座標位置。輸出兩個整數表示離漁夫最近的魚群中心座標,保證最近的魚群只有一個。
5 6
1
10 10
10 10
8 2
3
7 9
10 3
5 1
10 3
20 15
7
25 34
100 0
12 51
3 9
37 22
10 71
2 36
3 9

解題思路

因為計算座標距離會需要用到根號,可能會有無條件捨去或進位的錯誤發生導致誤判最小值,所以可以不用在計算座標時將答案進行根號計算。使用 For迴圈 判斷每一個座標跟船的距離,並且取最小值。

範例程式碼-ZeroJudge H658: 捕魚 (Fishing)

#include <iostream>
#include <math.h>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int x, y;
    cin >> x >> y;
    int N;
    cin >> N;
    int ans = 9999999;
    pair<int, int>loc;
    for (int i = 0; i<N; i++)
    {
        int a, b;
        cin >> a >> b;
        int dis = pow(a-x, 2) + pow(b-y, 2);
        if (dis < ans)
        {
            ans = dis;
            loc.first = a;
            loc.second = b;
        }
    }
    cout << loc.first << " " << loc.second << "\n";
}

//ZeroJudge H658
//Dr. SeanXD

發佈留言