g730 - 110北二1.矩形與點

🔗 前往 ZeroJudge 原題

題目描述

題目給定兩個矩形的八個頂點座標，以及一個點的座標。要求判斷該點是否在兩個矩形內，並輸出不在矩形內的數量。如果點在一個矩形內，則該矩形的計數器加一。最後輸出 2 減去計數器的結果。

解題思路

題目要求判斷點是否在矩形內，核心邏輯是檢查點的 x 座標是否在矩形 x 座標範圍內，且點的 y 座標是否在矩形 y 座標範圍內。程式碼中，min(a[i], a[i+2]) 和 max(a[i], a[i+2]) 計算矩形的 x 座標範圍，min(a[i+1], a[i+3]) 和 max(a[i+1], a[i+3]) 計算矩形的 y 座標範圍。迴圈遍歷兩個矩形，對於每個矩形，檢查點是否在其範圍內，如果是，則 ans 加一。最後，輸出 2 - ans。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int main(){
	int a[8],x,y,ans=0;
	for(int i=0;i<8;++i){
		cin >> a[i];
	}
	cin >> x >> y;
	for(int i=0;i<8;i+=4){
		if(x>min(a[i],a[i+2])&&x<max(a[i],a[i+2])&&y>min(a[i+1],a[i+3])&&y<max(a[i+1],a[i+3]))++ans;
	}
	cout << 2-ans;
}