f338 - 2. 后羿射日(Archer)

🔗 前往 ZeroJudge 原題

題目描述

題目描述了后羿射太陽的問題。給定后羿的座標、等級和射程，以及多個太陽的座標和等級，要求計算后羿能夠射下的太陽數量。射下太陽的條件是太陽的等級不超過后羿的等級，並且太陽與后羿的距離在射程範圍內。

解題思路

題目要求計算后羿可以射下的太陽數量。對於每個太陽，首先判斷其等級是否小於等於后羿的等級。如果等級符合條件，則計算后羿與太陽之間的距離。如果距離小於等於后羿的射程，則后羿可以射下該太陽，計數器加一。最後輸出計數器的值。距離計算使用平方避免開根號，提高效率。

複雜度分析

• 時間複雜度: O(n)，其中 n 是太陽的數量。需要遍歷所有太陽來判斷是否可以射下。
• 空間複雜度: O(1)，只需要常數級別的額外空間來存儲變量。

程式碼

#include <iostream>
using namespace std;
int main(){
	int x,y,l,r,m,ans=0,a,b,c;
	cin >> x >> y >> l >> r >> m;
	r*=r;
	while(m--){
		cin >> a >> b >> c;
		a-=x;
		b-=y;
		if(c<=l&&a*a+b*b<=r){
			++ans;
		}
	}
	cout << ans;
}