d091 - 00476 - Points in Figures: Rectangles
題目描述
題目給定一些矩形和一些點，要求判斷每個點是否包含在任何一個矩形內部。矩形由左上角和右下角的座標定義，點的座標則直接給定。如果點剛好落在矩形的邊上，則不視為包含在矩形內部。
解題思路
程式碼首先讀取矩形的資料，將每個矩形的座標儲存在 s 陣列中。讀取完矩形後，程式碼開始讀取點的座標，並對每個點進行判斷。對於每個點，程式碼遍歷所有矩形，檢查該點是否在矩形的內部。如果點的 x 座標大於矩形的左上角 x 座標且小於矩形的右下角 x 座標，並且點的 y 座標大於矩形的左上角 y 座標且小於矩形的右下角 y 座標，則認為該點包含在該矩形內部。如果點包含在任何一個矩形內部，則輸出相應的訊息。如果點不包含在任何矩形內部，則輸出 "Point i is not contained in any figure"。
複雜度分析
- 時間複雜度: O(N*M)，其中 N 是點的數量，M 是矩形的數量。因為對於每個點，都需要遍歷所有矩形進行判斷。
- 空間複雜度: O(M)，其中 M 是矩形的數量。因為程式碼需要儲存所有矩形的座標。
程式碼
#include <iostream>
using namespace std;
float s[10][4],a,b;
int sit,count;
char in;
int main(){
while(cin >> in){
if(in=='*')break;
else{
for(int i=0;i<4;++i)
cin >> s[sit][i];
++sit;
}
}
while(cin >> a >> b){
if(a>9999&&a<10000&&b>9999&&b<10000)break;
bool ans=0;
++count;
for(int i=0;i<sit;++i)
if(a>s[i][0]&&a<s[i][2]&&b>s[i][3]&&b<s[i][1]){
cout << "Point " << count << " is contained in figure " << i+1 << "\n";
ans=1;
}
if(!ans)
cout << "Point " << count << " is not contained in any figure\n";
}
}