but: 原图： 原题： [HBCPC2024] Lili Likes Polygons：

[HBCPC2024] Lili 喜欢多边形

题目描述

Lili 和 Nana 正在 Lili 家的后院除草。他们反复选择矩形区域并清除其中的所有草。

后院可以可视化为 2D 网格，每个方格代表一个单位面积。他们总共执行了 $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$次除草操作后，裸露区域的并集可能不相连，但所有边都是水平或垂直的。因此，并集变为正交多边形，其中一些包含多边形孔洞。此外，一些孔洞内可能存在裸露单元格。请参阅示例输入以获取更多详细信息和说明。

现在，他们想通过在裸露单元格上种植一些植物来恢复土地。Lili 喜欢多边形，尤其是矩形。因此，他们想选择几个矩形，这些矩形彼此不重叠，并且恰好覆盖所有裸露单元格。然后，他们在他们选择的不同矩形中种植不同的植物。

例如，对于上述情况，这里有一个可行的矩形选择：选择$[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 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 ### 样例输出 #1 4 ## 样例输入 #2 2 1 1 100 100 1 501 100 600 ### 样例输出 #2 2 ## 样例 #3 ### 样例输入 #3 4 1 1 4 1 1 4 5 4 1 1 1 4 4 1 4 5 ### 样例输出 #3 5 ## 样例 #4 ### 样例输入 #4 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 ### 样例输出 #4 9 ## 提示 对于第一个示例，最佳选择是 $[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]$。

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

[HBCPC2024] Lili Likes Polygons

题目描述

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.

样例 #1

样例输入 #1

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

样例输出 #1

4

样例 #2

样例输入 #2

2
1 1 100 100
1 501 100 600

样例输出 #2

2

样例 #3

样例输入 #3

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

样例输出 #3

5

样例 #4

样例输入 #4

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

样例输出 #4

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.