矩形
矩形
1.扫描线算法
2.线段树
3.矩形切割算法
4.坐标压缩
5.二维线段树
6.矩形树
7.树状数组
8.空间压缩
矩形面积一
描述
在二维平面上计算出两个由直线构成的矩形重叠后形成的总面积。
每个矩形由其左下顶点和右上顶点坐标表示，如图所示。
示例:
输入: -3, 0, 3, 4, 0, -1, 9, 2
输出: 45
分析
—-
矩形面积二
描述
链接
我们给出了一个（轴对齐的）矩形列表 rectangles 。 对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标，（x2，y2）是该矩形右上角的坐标。
找出平面中所有矩形叠加覆盖后的总面积。 由于答案可能太大，请返回它对 10 ^ 9 + 7 取模的结果。
示例 1：
输入：[[0,0,2,2],[1,0,2,3],[1,0,3,1]]
输出：6
解释：如图所示。
示例 2：
输入：[[0,0,1000000000,1000000000]]
输出：49
解释：答案是 10^18 对 (10^9 + 7) 取模的结果， 即 (10^9)^2 → (-7)^2 = 49 。
提示：
1 <= rectangles.length <= 200
rectanges[i].length = 4
0 <= rectangles[i][j] <= 10^9
矩形叠加覆盖后的总面积不会超越 2^63 - 1 ，这意味着可以用一个 64 位有符号整数来保存面积结果。
分析
容斥原理
—-
坐标压缩,扫描每个格子
—-
线性扫描 水平线段 垂直间隔
—-
扫描 水平线段树 垂直间隔
完美矩形
描述
链接
我们有 N 个与坐标轴对齐的矩形, 其中 N > 0, 判断它们是否能精确地覆盖一个矩形区域。
每个矩形用左下角的点和右上角的点的坐标来表示。例如， 一个单位正方形可以表示为 [1,1,2,2]。 ( 左下角的点的坐标为 (1, 1) 以及右上角的点的坐标为 (2, 2) )。
示例 1:
rectangles = [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]
]
返回 true。5个矩形一起可以精确地覆盖一个矩形区域。
示例 2:
rectangles = [
[1,1,2,3],
[1,3,2,4],
[3,1,4,2],
[3,2,4,4]
]
返回 false。两个矩形之间有间隔，无法覆盖成一个矩形。
示例 3:
rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[3,2,4,4]
]
返回 false。图形顶端留有间隔，无法覆盖成一个矩形。
示例 4:
rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[2,2,4,4]
]
返回 false。因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。
分析
扫描线算法
矩形切割
根据面积求解
求出矩形区域的四个角，计算矩形区域的面积，然后再计算矩形覆盖的面积(参考矩形面积二)，判断两者是否相等
将问题转变成了求矩形覆盖面积问题
根据矩形各个点的特征和面积求解
1.矩形区域的四个角每个顶点出现一次
2.矩形区域边上的每个顶点出现两次
3.矩形内部的每个顶点出现四次或者两次
这三个条件是否可以保证矩形区域内都被覆盖了?
4.所有矩形的面积之和等于矩形区域面积
加上条件4就可以保证矩形没有重叠面积
根据这四个条件得到的结果是否可以保证答案正确
这种方法有些奇思妙想，很难证明正确性
Shaping Regions
描述
N opaque rectangles (1 <= N <= 1000) of various colors are placed on a white sheet of paper whose size is A wide by B long. The rectangles are put with their sides parallel to the sheet’s borders. All rectangles fall within the borders of the sheet so that different figures of different colors will be seen.
The coordinate system has its origin (0,0) at the sheet’s lower left corner with axes parallel to the sheet’s borders.
PROGRAM NAME: rect1
INPUT FORMAT
Line 1: A, B, and N, space separated (1 <= A,B <= 10,000)
Lines 2-N+1: Five integers: llx, lly, urx, ury, color: the lower left coordinates and upper right coordinates of the rectangle whose color is `color’ (1 <= color <= 2500) to be placed on the white sheet. The color 1 is the same color of white as the sheet upon which the rectangles are placed.
—-
N个不同颜色的矩形依次被堆放在一个宽A长B的矩形白纸上，求俯视视角中各种颜色所占的面积