b182 - 3. 矩形的內部與外部
題目描述
題目要求計算給定點被多個矩形包含的總面積。輸入包含矩形的數量和座標，以及查詢點的數量和座標。對於每個查詢點，程式需要遍歷所有矩形，判斷點是否在矩形內部，並將包含該點的矩形面積累加。
解題思路
程式首先讀取矩形的數量 a 和查詢點的數量 b。然後，對於每個矩形，讀取其四個座標，並確保座標的順序是左下角和右上角。計算矩形的面積，並儲存起來。接著，對於每個查詢點，讀取其座標，遍歷所有矩形，判斷該點是否在矩形的範圍內。如果點在矩形內部，則將矩形的面積加到總面積中。最後，輸出每個查詢點的總面積。
複雜度分析
- 時間複雜度: O(a * b)，其中 a 是矩形的數量，b 是查詢點的數量。因為對於每個查詢點，都需要遍歷所有矩形。
- 空間複雜度: O(a * 5)，因為程式使用一個 a x 5 的二維陣列來儲存矩形資訊。
程式碼
#include <stdio.h>
int main(){
long long int a,b,x,y;
while(scanf("%lld%lld",&a,&b)>0){
long long int n[a][5];
for(long long int i=0;i<a;i++){
scanf("%lld%lld%lld%lld",&n[i][0],&n[i][1],&n[i][2],&n[i][3]);
if(n[i][0]>n[i][2]){
n[i][0]^=n[i][2];
n[i][2]^=n[i][0];
n[i][0]^=n[i][2];
}
if(n[i][1]>n[i][3]){
n[i][1]^=n[i][3];
n[i][3]^=n[i][1];
n[i][1]^=n[i][3];
}
n[i][4]=(n[i][2]-n[i][0])*(n[i][3]-n[i][1]);
}
for(long long int i=0,ans=0;i<b;i++,ans=0){
scanf("%lld%lld",&x,&y);
for(long long int ii=0;ii<a;ii++){
if(x>=n[ii][0]&&x<=n[ii][2]&&y>=n[ii][1]&&y<=n[ii][3]){
ans+=n[ii][4];
}
}
printf("%lld\n",ans);
}
}
return 0;
}