Description

After several harsh winters, Farmer John has decided it is time to repaint his farm. The farm consists of $N$ fenced enclosures ($1 \le N \le 50000$), each represented by a rectangle in the 2D plane whose sides are parallel to the $x$ and $y$ axes. Enclosures may be nested (one fully contained within another), but no two fences intersect or touch. Therefore, if two enclosures cover the same region of the 2D plane, one must be contained within the other.

Farmer John figures that an enclosure contained within another will not be visible from the outside world, so he only wants to repaint enclosures that are not contained within any other enclosures. Please determine the total number of enclosures he needs to paint.

Input Format

• Line 1: The number of enclosures, $N$.
• Lines 2..$N+1$: Each line describes an enclosure with four space-separated integers $x_1$, $y_1$, $x_2$, and $y_2$, where $(x_1, y_1)$ is the lower-left corner and $(x_2, y_2)$ is the upper-right corner. All coordinates are in the range 0..1,000,000.

Output Format

• Line 1: The number of enclosures that are not contained within any other enclosures.

3 
2 0 8 9 
10 2 11 3 
4 2 6 5 

2 

Hint

There are three enclosures. The first has corners $(2, 0)$ and $(8, 9)$, and so on. Enclosure 3 is contained within enclosure 1, so there are two enclosures not contained within other enclosures.

Translated by ChatGPT 5