平面内有n个矩形, 第i个矩形的左下角坐标为(x1[i], y1[i]), 右上角坐标为(x2[i], y2[i])。
如果两个或者多个矩形有公共区域则认为它们是相互重叠的(不考虑边界和角落)。
请你计算出平面内重叠矩形数量最多的地方,有多少个矩形相互重叠。
平面内有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。
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))
""" 重叠的区域角横坐标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)
啊!!!有没有大佬可以帮我看看,卡在最后一组用例上了,90%最后一组答案是10,我的结果是9.很难过啊!!!!!