h658 - 捕魚 (Fishing)

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個漁夫的位置 (x, y) 和 t 個魚的位置 (xx, yy)。目標是找到距離漁夫最近的魚的位置，並輸出該魚的座標。

解題思路

這題的解題思路是遍歷所有魚的位置，計算每個魚與漁夫之間的距離，並記錄下距離最小的魚的位置。使用貪心策略，每次更新當前最小距離和對應的魚的位置。距離計算使用歐幾里得距離公式：sqrt((x - xx)^2 + (y - yy)^2)。由於只需要找到最小距離，因此不需要對距離進行排序。

複雜度分析

• 時間複雜度: O(t)，其中 t 是魚的數量。需要遍歷所有魚的位置一次。
• 空間複雜度: O(1)，只需要常數級別的額外空間來存儲變數，例如最小距離、魚的座標等。

程式碼

#include <iostream>
using namespace std;
int x,y,t,xx,yy,ans=1e9,ax,ay;
int main(){
	cin >> x >> y >> t;
	while(t--){
		cin >> xx >> yy;
		if((x-xx)*(x-xx)+(y-yy)*(y-yy)<ans){
			ans=(x-xx)*(x-xx)+(y-yy)*(y-yy);
			ax=xx;
			ay=yy;
		}
	}
	cout << ax << " " << ay;
}