首页 > 试题广场 >

矩形重叠

[编程题]矩形重叠
  • 热度指数:327 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

平面内有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().strip().split()))
y1 = list(map(int, input().strip().split()))
x2 = list(map(int, input().strip().split()))
y2 = list(map(int, input().strip().split()))
N = len(x1)
matrix = []
for i in range(n):
    matrix.append([x1[i],y1[i],x2[i],y2[i]])
d = sorted(matrix,key = lambda x : x[0])
d = sorted(d,key = lambda x : x[1])
count = 1
res = 0
for i in range(1,len(d)):
    if (d[i][0] < d[i-1][2] and d[i][1] <= d[i-1][3]) or (d[i][0] <= d[i-1][2] and d[i][1] < d[i-1][3]):
        count +=1
        res = max(count,res)
    else:
        count = 1
        
if res == 0:
    res = 1
print(res)
通过率50% 为什么呢
发表于 2019-08-02 22:53:17 回复(0)
思想为这篇文章中的 https://www.nowcoder.com/discuss/70736
换成python实现一下,通过率100%
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()))
# 将所有原矩形的(x1,y1,x2,y2)坐标分别整理为 x坐标集合 & y坐标集合
x_set = x1 + x2
y_set = y1 + y2
ans = 0
# 依次枚举其中任意一对(x,y)所构成的子矩形
for x in x_set:
   for y in y_set:
       cnt = 0
       for i in range(n):
           if (x1[i] <=x and y1[i] <=y and x2[i] > x and y2[i] > y): # 统计比这个子矩形大(完全能包裹住该子矩形)的原矩形有多少个
               cnt += 1
       ans = max(ans, cnt) # 每检查完一个子矩形,就更新一次当前的计数最大值
print(ans)
没有系统学过算法与数据结构...最开始想的方法是,
创建一个全0矩阵然后依次遍历每一个矩形,把矩形内部的点在原来的数值上加1,最后统计矩阵中最大值。但是这种方法太暴力会超内存哈哈,通过率40%
编辑于 2019-07-08 23:10:33 回复(1)