小明是名漁翁,每天都會到開著船到大海去捕魚。捕魚是他熱愛的興趣,為了更有效率的捕獲最多的魚,小明會利用船上的雷達系統來探測週遭的魚群,這樣就可以知道每群與船隻的距離,藉此從最近的地方開始捕獲。
小明希望利用程式快速找到離自己最近的魚群,請你幫幫他。
範例測資
範例輸入 | 範例輸出 |
---|---|
輸入第一列有兩個整數 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