Escape, Polygon!

Time limit2sMemory limit512 MB

Summary

Given an integer convex polygon of up to 100000 vertices, count the triples of its sides whose supporting lines form a triangle containing the polygon. Output that count.

Level: Hard8 of 10
Topics: Geometry, Combinatorics, Sorting, Math
Solved: No attempts yet

Problem

A suspicious-looking convex polygon wants to escape its current position by translating itself along some straight-line direction. Three very diligent straight lines want to lock it up by placing themselves along three distinct sides of the polygon. If the triple of lines defines a triangle and the polygon lies inside this triangle, it is locked up. Otherwise, it escapes.

Figure (a) above illustrates a triple that locks the polygon up. For (b), the lines do not define a triangle since two of them are parallel, so the polygon escapes. In (c), the polygon lies outside the triangle defined by the triple and easily escapes.

Given a polygon, compute the number of distinct triples of lines that can lock the polygon up.

Input

The first line contains an integer N (3 ≤ N ≤ 105) representing the number of vertices of the polygon. Each of the next N lines describes a vertex with two integers X and Y (−108 ≤ X, Y ≤ 108) indicating the coordinates of the vertex in the XY plane. The vertices are given in counter-clockwise order and they define a simple convex polygon. No three vertices are collinear.

Output

Output a single line with an integer indicating the number of distinct triples of lines that can lock the given polygon up.

Examples5

Example 1
Input
```
4
0 0
10 0
10 10
0 5
```
Expected output
```
1
```

Example 2

Input

Expected output

Example 3
Input
```
3
10 -10
0 10
-10 -10
```
Expected output
```
1
```

Example 4

Input

6
-100000000 131
-50000067 -100000000
50000014 -100000000
100000000 -109
70000173 100000000
-90000011 100000000

Expected output

Example 5
Input
```
4
0 0
10 0
10 10
0 10
```
Expected output
```
0
```