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
標籤

相關文章

發佈留言