Segment Intersection 1

Interview

Time limit0.25sMemory limit512 MB

Summary

Given the integer endpoints of two segments, decide whether the segments intersect, using orientation tests with no three input points collinear.

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

Problem

Given two line segments $L_1$ and $L_2$ on the two-dimensional coordinate plane, determine whether the two segments intersect.

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$ . No three points lie on the same line.

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.
The length of each segment is greater than 0.

Examples2

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
```