Line Segment Intersection 4

Time limit1sMemory limit512 MB

Summary

Given N line segments with integer endpoints, determine whether any two segments intersect, counting endpoint touches and overlaps as intersections.

Level: Medium7 of 10
Topics: Geometry, Sorting, Tree
Solved: No attempts yet

Problem

A set of N line segments is given on the two-dimensional coordinate plane. Determine whether there exist two segments that intersect. If an endpoint of one segment lies on another segment or coincides with another segment's endpoint, the two segments count as intersecting.

Input

The first line contains the number of segments N. Each of the next N lines contains four integers x1, y1, x2, y2, which are the two endpoints (x1, y1) and (x2, y2) of a segment.

Output

If there are two intersecting segments, print 1. Otherwise, print 0.

Constraints

1 ≤ N ≤ 200,000
$-10^9 \le x_i, y_i \le 10^9$
$x_i$ and $y_i$ are integers.
Each segment has a length greater than 0.

Examples5

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