d093 - 00477 - Points in Figures: Rectangles and Circles
題目描述
題目給定一些矩形和圓形，以及一些點的座標。要求判斷每個點是否包含在任何一個圖形內，並輸出結果。如果點落在圖形邊界上，則不視為包含在圖形內。
解題思路
程式首先讀取圖形的資料，將矩形和圓形的資訊儲存在 arr 陣列中。對於每個點，程式遍歷所有圖形，檢查該點是否在矩形或圓形的範圍內。如果是矩形，則檢查點的 x 座標是否在矩形的左右邊界之間，且 y 座標是否在矩形的上下邊界之間。如果是圓形，則計算點到圓心的距離，如果距離小於圓的半徑，則認為點在圓內。如果點在任何一個圖形內，則輸出相應的訊息。如果點不在任何圖形內，則輸出 "Point i is not contained in any figure"。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 是點的數量，m 是圖形的數量。因為對於每個點，都需要遍歷所有圖形進行判斷。
- 空間複雜度: O(m)，其中 m 是圖形的數量。因為需要儲存所有圖形的資訊。
程式碼
#include <iostream>
using namespace std;
float arr[11][5];
int it;
int main(){
float x,y;
char a;
while(cin >> a){
if(a=='*')break;
else if(a=='c'){
cin >> arr[it][1] >> arr[it][2] >> arr[it][3];
arr[it][3]*=arr[it][3];
}
else{
arr[it][0]=1;
cin >> arr[it][1] >> arr[it][2] >> arr[it][3] >> arr[it][4];
}
++it;
}
int c=0;
while(cin >> x >> y){
if(x>9999&&x<10000&&y>9999&&y<10000)break;
bool k=0;
++c;
for(int i=0;i<it;++i){
if(arr[i][0]){
if(arr[i][1]<x&&arr[i][3]>x&&arr[i][2]>y&&arr[i][4]<y){
cout << "Point " << c << " is contained in figure " << i+1 << "\n";
k=1;
}
}
else{
float xx=arr[i][1]-x;
float yy=arr[i][2]-y;
if(xx*xx+yy*yy<arr[i][3]){
cout << "Point " << c << " is contained in figure " << i+1 << "\n";
k=1;
}
}
}
if(k==0)
cout << "Point " << c << " is not contained in any figure\n";
}
}