P10860 [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.

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.