牛客矩形重叠

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

题目描述

平面内有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

输入

输出

import sys

lines = sys.stdin.readlines()

n = int(lines[0].strip().split()[0])
x1 = list(map(int, lines[1].strip().split()))
y1 = list(map(int, lines[2].strip().split()))
x2 = list(map(int, lines[3].strip().split()))
y2 = list(map(int, lines[4].strip().split()))

ans = 0
for a in x1 + x2:
    for b in y1 + y2:
        count = 0
        for i in range(n):
            if x1[i] < a <= x2[i] and y1[i] < b <= y2[i]:
                count += 1
        ans = max(ans, count)
    
print(ans)

牛客 矩形重叠

Contact me:

牛客矩形重叠