【2019校招真题】矩形重叠（python）
题目描述
平面内有n个矩形, 第i个矩形的左下角坐标为(x1[i], y1[i]), 右上角坐标为(x2[i], y2[i])。
如果两个或者多个矩形有公共区域则认为它们是相互重叠的(不考虑边界和角落)。
请你计算出平面内重叠矩形数量最多的地方,有多少个矩形相互重叠。
输入描述:
输入包括五行。 第一行包括一个整数n(2 <= n <= 50), 表示矩形的个数。 第二行包括n个整数x1[i](-10^9 <= x1[i] <= 10^9),表示左下角的横坐标。 第三行包括n个整数y1[i](-10^9 <= y1[i] <= 10^9),表示左下角的纵坐标。 第四行包括n个整数x2[i](-10^9 <= x2[i] <= 10^9),表示右上角的横坐标。 第五行包括n个整数y2[i](-10^9 <= y2[i] <= 10^9),表示右上角的纵坐标。
输出描述:
输出一个正整数, 表示最多的地方有多少个矩形相互重叠,如果矩形都不互相重叠,输出1。
示例1
输入
2 0 90 0 90 100 200 100 200
输出
2
解题思路
遍历所有的点，求出有多少点包含当前点。
完整代码
n = int(input())
x1 = list(map(int, input().split()))
y1 = list(map(int, input().split()))
x2 = list(map(int, input().split()))
y2 = list(map(int, input().split()))
res = 1
for x in x1 + x2:
for y in y1 + y2:
cnt = 0
for i in range(n):
if x > x1[i] and x <= x2[i] and y > y1[i] and y <= y2[i]:
cnt += 1
res = max(res, cnt)
print(res) 