a879 - A.君不見 黃色小鴨水上漂
題目描述
題目描述了在雞隆港舉辦黃色小鴨展覽時，需要計算在觀景台指定視野範圍內可見的小鴨數量。給定小鴨和觀景台的座標，以及觀景台的視野半徑，計算有多少隻小鴨在視野範圍內。
解題思路
題目要求計算在圓形視野範圍內的小鴨數量。解題思路是遍歷每一隻小鴨，計算小鴨與觀景台之間的距離，如果距離小於或等於視野半徑，則認為該小鴨可見。為了避免浮點數誤差，題目提示不需要使用開根號函數，而是直接比較距離的平方與視野半徑的平方。
複雜度分析
- 時間複雜度: O(N)，其中 N 是小鴨的數量。需要遍歷每一隻小鴨來計算距離。
- 空間複雜度: O(N)，用於儲存小鴨的座標。
程式碼
#include <iostream>
using namespace std;
int main(int argc, char** argv){
cin.tie(0);
ios::sync_with_stdio(false);
int a,b,c,h;
cin>>a;
while(a--){
h=0;
cin>>b>>c;
int d[b][2],f[2];
for(int e=0;e<b;e++)
cin>>d[e][0]>>d[e][1];
cin>>f[0]>>f[1];
for(int g=0;g<b;g++){
if(c*c<(d[g][0]-f[0])*(d[g][0]-f[0])+(d[g][1]-f[1])*(d[g][1]-f[1]))
h++;
}
cout<<b-h<<"\n";
}
}