Farm Painting

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 50,000 non-intersecting axis-aligned rectangles, count how many are not contained inside any other rectangle.

Level: Medium6 of 10
Topics: Sorting, Array, Geometry, Brute force
Solved: No attempts yet

Problem

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 50{,}000$ ), each of which can be described by a rectangle in the 2D plane whose sides are parallel to the $x$ - and $y$ -axes.

An enclosure may be contained inside another enclosure, but no two fences ever intersect. Consequently, if two enclosures cover the same area of the plane, one of them must be completely contained within the other.

An enclosure contained inside another enclosure is hidden from the outside world, so Farmer John only wants to repaint the enclosures that are not contained within any other enclosure. Determine the total number of enclosures he needs to paint.

Input

The first line contains the number of enclosures, $N$ .
Each of the next $N$ lines describes one enclosure with four space-separated integers $x_1$ , $y_1$ , $x_2$ , $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 integers between $0$ and $1{,}000{,}000$ , inclusive.

Output

Print a single line with the number of enclosures that are not contained within any other enclosure.

Hint

Because no two fences intersect, whenever two enclosures cover the same region one of them must lie entirely inside the other. You only need to count the enclosures that are not nested inside any other enclosure.

Examples3

Example 1
Input
```
3
2 0 8 9
10 2 11 3
4 2 6 5
```
Expected output
```
2
```
Example 2
Input
```
2
0 0 10 10
2 2 8 8
```
Expected output
```
1
```
Example 3
Input
```
2
0 0 5 5
10 10 20 20
```
Expected output
```
2
```