Intersecting Rectangles

You are given a set of $n$ axis-aligned rectangles in a 2D plane. For this problem, two rectangles are considered to intersect if their boundaries contain any common points (in particular, two nesting rectangles donâ€™t count as intersecting). Determine if some pair of rectangles intersect.

In this example, only rectangles **A** and
**B** intersect.

Each test case will begin with a line with a single integer $n$ ($1\! \le \! n\! \le \! 10^5$), which is the number of rectangles.

Each of the next $n$ lines will contain four space-separated integers:

($-10^9\! \le \! x_1,y_1,x_2,y_2\! \le \! 10^9, x_1\! <\! x_2, y_1\! <\! y_2$), which describe a rectangle, where $(x_1,y_1)$ is the lower left corner and $(x_2,y_2)$ is the upper right corner. All $x$ values will be distinct. All $y$ values will be distinct.

Output a single integer, which is $1$ if some pair of rectangles intersect, $0$ if no pair of rectangles intersect.

Sample Input 1 | Sample Output 1 |
---|---|

3 0 0 2 2 1 1 3 4 5 7 6 8 |
1 |

Sample Input 2 | Sample Output 2 |
---|---|

4 0 0 20 20 1 1 3 4 2 10 9 12 11 3 19 18 |
0 |