首页 > 试题广场 >

矩形重叠

[编程题]矩形重叠
  • 热度指数:22586 时间限制: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
import sys

lines = sys.stdin.readlines()    
n = int(lines[0])
for i in range(4):
    lines[i] = lines[i + 1].split()
    lines[i] = [int(i) for i in lines[i]]
recs = []
for i in range(n):
    recs.append((lines[0][i], lines[1][i], lines[2][i], lines[3][i]))
# recs是一个由所有矩形构成的列表
    
def make_rec(rec_1, rec_2):
    """由两个矩形生成一个新矩形,if判断两个矩形是否相交。若不相交则返回None"""

    if rec_2[0] < rec_1[2] and rec_2[1] < rec_1[3] and rec_2[2] > rec_1[0] and rec_2[3] > rec_1[1]:
        return (max(rec_1[0], rec_2[0]), max(rec_1[1], rec_2[1]), min(rec_1[2], rec_2[2]), min(rec_1[3], rec_2[3]))


def count(recs):
    """动态规划"""

    n = len(recs)
    if n == 0:
        return 0    
    recs_new = []
    
    for i in range(0, n - 1):
        rec_new = make_rec(recs[n - 1], recs[i])
        if rec_new:
            recs_new.append(rec_new)

    recs.pop()
    return max(count(recs_new) + 1, count(recs))
    
print(count(recs))

发表于 2020-03-24 15:15:31 回复(0)
"""
重叠的区域角横坐标x必然是【x1,x2】中某个值
重叠的区域角横坐标y必然是【y1,y2】中某个值
遍历所有坐标点(x,y),由于重叠不考虑边界和角落
    在 x_range, y_range = x ± δ, y ± δ (δ< 1)
    x1[i] < x_range < x2[i] and y1[i] < y_range < y2[i] 范围内计算重叠个数
    或者 x1[i] < x <= x2[i] and y1[i] < y <= y2[i] ,等号的位置等同于上式的±号。
取所有坐标点最大的重叠个数即为所求
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open('input.txt', 'r')
    n = int(input().strip())
    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()))
    ans = 1
    for x in x1 + x2:
        for y in y1 + y2:
            x_range, y_range = x - 0.1, y - 0.1
            cnt = 0
            for i in range(n):
                if x1[i] < x_range < x2[i] and y1[i] < y_range < y2[i]:
                # if x1[i] < x <= x2[i] and y1[i] < y <= y2[i]:
                    cnt += 1
            ans = max(ans, cnt)
    print(ans)

发表于 2019-07-02 19:55:20 回复(3)
import sys

if __name__ == "__main__":
lines = sys.stdin.readlines()
n = int(lines[0])
x1 = list(map(int,lines[1].split()))
y1 = list(map(int,lines[2].split()))
x2 = list(map(int,lines[3].split()))
y2 = list(map(int,lines[4].split()))
    max_c = 1
    for i in range(n):
        ax1 = x1[i]
        ay1 = y1[i]
        ax2 = x2[i]
        ay2 = y2[i]
        count = 1
        for j in range(n):
            if i == j:
                continue
            bx1 = x1[j]
            by1 = y1[j]
            bx2 = x2[j]
            by2 = y2[j]
            if by1 < ay2 and bx2 > ax1 and bx1 < ax2 and by2 > ay1:
                count += 1
                ax1 = max(ax1, bx1)
                ay1 = max(ay1, by1)
                ax2 = min(ax2, bx2)
                ay2 = min(ay2, by2)
        max_c = count if count > max_c else max_c
    print(max_c)
啊!!!有没有大佬可以帮我看看,卡在最后一组用例上了,90%最后一组答案是10,我的结果是9.很难过啊!!!!!

发表于 2018-03-28 23:29:35 回复(3)