Cow Steeplechase

Time limit1sMemory limit128 MB

Summary

Choose as many of N axis-parallel segments as possible so that no two chosen segments share any point.

Level: Medium7 of 10
Topics: Graph, Union-find, Geometry, Greedy
Solved: No attempts yet

Problem

Farmer John has a brilliant idea for the next great spectator sport: Cow Steeplechase! As everyone knows, regular steeplechase involves a group of horses that race around a course filled with obstacles they must jump over. FJ figures the same contest should work with highly-trained cows, as long as the obstacles are made short enough.

To design his course, FJ makes a diagram of all the $N$ ( $1 \le N \le 250$ ) possible obstacles he could build. Each one is a line segment in the 2D plane that is parallel to the horizontal or the vertical axis. Obstacle $i$ has distinct endpoints $(X1_i, Y1_i)$ and $(X2_i, Y2_i)$ , with $1 \le X1_i, Y1_i, X2_i, Y2_i \le 10^9$ . An example layout is:

   --+-------   
-----+-----
  ---+---     |
     |     |  |
   --+-----+--+-   |
     |     |  |  | |
     |   --+--+--+-+-
           |  |  | |
              |

FJ would like to build as many obstacles as possible, subject to the constraint that no two of them intersect. Starting from the diagram above, FJ can build 7 obstacles:

   ----------   
-----------
  -------     |
           |  |
           |  |    |
           |  |  | |
           |  |  | |
           |  |  | |
              |

Two segments intersect if they share any point in common, even an endpoint of one or both segments. You may assume that no two horizontal segments in the input intersect, and likewise no two vertical segments in the input intersect.

Determine the maximum number of obstacles FJ can build.

Input

Line 1: A single integer $N$ .
Lines 2 to $N+1$ : Line $i+1$ contains four space-separated integers describing obstacle $i$ : $X1_i$ , $Y1_i$ , $X2_i$ , and $Y2_i$ .

Output

Line 1: The maximum number of pairwise non-intersecting segments FJ can choose.

Hint

In the sample there are three candidate obstacles: a horizontal segment from $(4, 5)$ to $(10, 5)$ , and two vertical segments, one from $(6, 2)$ to $(6, 12)$ and one from $(8, 3)$ to $(8, 5)$ . The horizontal segment crosses both vertical segments, so at most two obstacles can be built. Choosing the two vertical segments, which do not intersect each other, yields the optimal answer of 2.

Examples1

Example 1
Input
```
3
4 5 10 5
6 2 6 12
8 3 8 5
```
Expected output
```
2
```