题目描述

Lili and Nana are weeding in the backyard of Lili’s house. They are repeatedly selecting rectangular areas and removing all the grass within them.

The backyard can be visualized as a 2D grid, each square cell representing one unit area. They have performed a total of $n$ operations. During the $i$-th operation, they choose the left, bottom, right, and top sides of a rectangle, denoted as $l_i, b_i, r_i, t_i$, and clear all the cells within this rectangle using a lawnmower. Note that these rectangles may overlap with each other.

Let $[l_i, r_i]\times[b_i, t_i]$ denote a rectangle.

Here is an example illustrated in the following figure. They have selected $2$ rectangles, with the first rectangle being $[1, 5]\times[2, 3]$ and the second rectangle being $[2, 3]\times[1, 4]$.

After the $n$ weeding operations, the union of the bare area may not be connected but all the sides are horizontal or vertical. Thus, the union becomes orthogonal polygon(s), some of which contain polygon holes. Moreover, there can be bare cells inner some holes. Please see the example inputs for more details and illustrations.

Now, they want to restore the land by planting some plants on the bare cells. Lili likes polygons, especially rectangles. Therefore, they want to select several rectangles, and these rectangles do not overlap with each other and exactly cover all the bare cells. Then, they plant different plants in different rectangles they selected.

For example, here is a feasible selection of rectangles for the aforementioned case: choose $[1, 1]\times [2, 3]$, $[2, 3]\times[1, 4]$ and $[4, 5]\times [2, 3]$.

After playing for a while, these two little girls have become tired, so they want to know the minimum number of non-overlapping rectangles that can cover all the bare cells.

输入格式

The first line contains a single integer $n$ ($1\leq n\leq 300$) --- the number of rectangles when they weed.

The following $n$ lines each contain $4$ integers, and the $i$-th line contains $l_i, b_i, r_i, t_i$ ($1\leq l_i, b_i, r_i, t_i\leq 10^9, l_i\leq r_i, b_i\leq t_i$) --- the left, bottom, right, and top sides of the $i$-th rectangle.

It is guaranteed the sum of the endpoints of the bare area (polygon(s) with polygonal holes) does not exceed $2000$.

输出格式

Output a single integer on a single line denoting the minimum number of rectangles they need to select to plant plants on all the bare cells.

题目大意

题目描述

莉莉和娜娜正在莉莉家后院除草。她们反复选择矩形区域，并移除其中的所有草坪。

后院可以被视为一个二维网格，每个方格表示一个单位面积。她们共进行了 $n$ 次操作。在第 $i$ 次操作中，她们选择了一个矩形的左、下、右、上的边界，分别表示为 $l_i, b_i, r_i, t_i$，并使用割草机清除该矩形内的所有方格。注意，这些矩形可能会相互重叠。

用 $[l_i, r_i] \times [b_i, t_i]$ 表示一个矩形。

以下是一个例子，如图所示。她们选择了 $2$ 个矩形，第一个矩形是 $[1, 5] \times [2, 3]$，第二个矩形是 $[2, 3] \times [1, 4]$。

经过 $n$ 次除草操作后，裸露区域的联合可能不连通，但所有边都是水平或垂直的。因此，联合区域变成了一个或多个直角多边形，其中一些可能包含多边形孔洞。此外，在某些孔洞内部可能会有裸露的方格。更多细节和图示请参见示例输入。

现在，她们想通过在裸露的方格上种植植物来恢复土地。莉莉喜欢多边形，特别是矩形。因此，她们想选择若干个矩形，这些矩形之间不重叠，并且能够完全覆盖所有的裸露方格。然后，她们将在选择的不同矩形中种植不同的植物。

例如，下面是上述情况的一个可行的矩形选择：选择 $[1, 1] \times [2, 3]$、$[2, 3] \times [1, 4]$ 和 $[4, 5] \times [2, 3]$。

玩了一会儿，这两个小女孩已经累了，所以她们想知道覆盖所有裸露方格的最小不重叠矩形数量。

输入格式

第一行包含一个整数 $n$ ($1 \leq n \leq 300$) —— 表示除草时使用的矩形数量。

接下来的 $n$ 行每行包含 $4$ 个整数，第 $i$ 行包含 $l_i, b_i, r_i, t_i$ ($1 \leq l_i, b_i, r_i, t_i \leq 10^9, l_i \leq r_i, b_i \leq t_i$) —— 表示第 $i$ 个矩形的左、下、右、上边界。

保证裸露区域的端点总数（多边形及其孔洞）不超过 $2000$。

输出格式

在一行上输出一个整数，表示覆盖所有裸露方格所需选择的最小矩形数量。

说明/提示

对于第一个例子，最优选择是 $[1, 1] \times [1, 3]$、$[2, 1] \times [2, 1]$、$[2, 3] \times [2, 3]$ 和 $[3, 1] \times [3, 3]$。

对于第二个例子，最优选择是 $[1, 1] \times [100, 100]$ 和 $[1, 501] \times [100, 600]$。

对于第三个例子，最优选择是 $[1, 1] \times [4, 1]$、$[1, 4] \times [5, 4]$、$[1, 2] \times [1, 3]$、$[4, 2] \times [4, 3]$ 和 $[4, 5] \times [4, 5]$。

对于第四个例子，裸露区域如下图所示。

翻译者：Immunoglobules

8
1 1 1 1
1 2 1 2
1 3 1 3
2 1 2 1
2 3 2 3
3 1 3 1
3 2 3 2
3 3 3 3

4

2
1 1 100 100
1 501 100 600

2

4
1 1 4 1
1 4 5 4
1 1 1 4
4 1 4 5

5

9
1 1 9 1
1 1 1 9
1 9 9 9
9 1 9 9
3 3 7 3
3 3 3 7
3 7 7 7
7 3 7 7
5 5 5 5

9

提示

For the first example, an optimal selection is $[1, 1]\times [1, 3]$, $[2, 1]\times [2, 1]$, $[2, 3]\times [2, 3]$ and $[3, 1]\times [3, 3]$.

For the second example, an optimal selection is $[1, 1]\times [100, 100]$ and $[1, 501]\times [100, 600]$.

For the third example, an optimal selection is $[1, 1]\times [4, 1]$, $[1, 4]\times [5, 4]$, $[1, 2]\times [1, 3]$, $[4, 2]\times [4, 3]$ and $[4, 5]\times [4, 5]$.

For the fourth example, the bare area is illustrated in the following figure.