Line Segment Intersection 2

Interview

Time limit0.25sMemory limit512 MB

Summary

Given two line segments by their integer endpoints, decide whether they intersect, counting endpoint touching as an intersection.

Level: Medium6 of 10
Topics: Geometry, Math, Implementation, Brute force
Solved: No attempts yet

Problem

Given two line segments $L_1$ and $L_2$ in the two-dimensional coordinate plane, determine whether the two segments intersect. A case where an endpoint of one segment lies on the other segment or on its endpoint also counts as an intersection.

The endpoints of $L_1$ are $(x_1, y_1)$ and $(x_2, y_2)$ , and the endpoints of $L_2$ are $(x_3, y_3)$ and $(x_4, y_4)$ .

Input

The first line gives the endpoints $x_1, y_1, x_2, y_2$ of $L_1$ , and the second line gives the endpoints $x_3, y_3, x_4, y_4$ of $L_2$ .

Output

Print 1 if $L_1$ and $L_2$ intersect, and 0 otherwise.

Constraints

$-1\,000\,000 \le x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4 \le 1\,000\,000$
$x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4$ are integers.
Each segment has length greater than 0.

Examples5

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