首页 > 试题广场 >

完美矩形 题目描述 给定n个轴对齐的矩形

[问答题]

完美矩形


题目描述

给定n个轴对齐的矩形其中n>0, 判断他们组合在一起能否覆盖一个完美的矩形区域(无重叠,无空隙)

每个矩形使用左下和右上的点表示。例如,一个矩形的定义为 [1,1,2,2],(左下坐标点 (1, 1) 和右上坐标点 (2, 2)的一个单元的正方形)。

输入

输入包含一组数据,有n行,每行代表一个矩形 (左下坐标点和右上坐标点),数字用空格隔开。

输出

对于每个测试实例,输出能否组合覆盖一个矩形(true/false) 。

输入样例

1 1 3 3

3 1 4 2

3 2 4 4

1 3 2 4

2 3 3 4

输出样例

true


推荐

题目解析:

本题有一定难度,需要遍历每个矩形,遍历过程中与前面矩形是否有重叠,并调整最小公共父矩形的数值,最后判断所有矩形面积是否与父矩形一样。

测试数据集
输入:

1 1 3 3
3 1 4 2
3 2 4 4
1 3 2 4
2 3 3 4

输出:true

输入:

1 1 3 3
3 1 4 2
3 2 4 4
1 3 2 4
2 3 3 4

输出:
false

输入:

1 1 2 3
1 3 2 4
3 1 4 2
3 2 4 4

输出:false

输入:

1 1 3 3
3 1 4 2
1 3 2 4
2 2 4 4

输出:false
发表于 2018-08-01 21:20:28 回复(0)