Convex Polygons

Time limit1sMemory limit1024 MB

Summary

Find the longest contiguous run of points that forms a convex polygon in counterclockwise order, and report its length.

Level: Medium7 of 10
Topics: Array, Two pointers, Geometry
Solved: No attempts yet

Problem

A set of $N$ points $P_1, P_2, \ldots, P_N$ is given on the 2D coordinate plane. Find the maximum value of $r - l + 1$ over all integers $l$ and $r$ that satisfy the following conditions.

$1 \le l < r \le N$ , and $r - l + 1 \ge 3$ .
$P_l, P_{l+1}, \ldots, P_r$ form a convex polygon in counterclockwise order. Every interior angle is less than 180 degrees.

Input

The first line contains the number of points $N$ . ( $3 \le N \le 300000$ )

Each of the next $N$ lines contains two integers $x_i$ and $y_i$ , the x and y coordinates of the $i$ -th point. ( $-10^9 \le x_i, y_i \le 10^9$ )

All given points are distinct.

Output

Print the maximum value of $r - l + 1$ over all pairs $l$ and $r$ that satisfy the conditions. If no such pair exists, print $-1$ .

Hint

A convex polygon is a simple polygon (one that does not cross itself) where every segment joining two points on its boundary stays inside the polygon.

Examples2

Example 1
Input
```
3
1 1
2 2
3 3
```
Expected output
```
-1
```
Example 2
Input
```
5
3 1
4 2
5 9
6 2
7 4
```
Expected output
```
3
```