Triangle Counting

Time limit1sMemory limit128 MB

Summary

Count how many triangles formed by triples of N integer points strictly contain the origin in their interior.

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

Problem

Bessie is on guard duty, watching the herd from her tower. To pass the time, she imagines the pasture as an $XY$ plane and studies where the cows are standing.

There are $N$ cows ( $1 \le N \le 100000$ ), numbered $1$ through $N$ . Cow $i$ stands at the integer coordinates $(X_i, Y_i)$ with $-100000 \le X_i, Y_i \le 100000$ . No cow stands on the origin $(0, 0)$ , and the origin never lies on the segment joining any two cows.

Bessie mentally forms every triangle whose three vertices are three different cows. She calls such a triangle golden if it strictly contains the origin in its interior.

Given all of the cow positions, determine how many of these triangles are golden.

Input

The first line contains one integer $N$ .
Each of the next $N$ lines contains two integers $X_i$ and $Y_i$ , the coordinates of one cow.

Output

Print one integer: the number of triangles, formed by three cows, that strictly contain the origin.

Examples7

Example 1
Input
```
5
-5 0
0 2
11 2
-11 -6
11 -5
```
Expected output
```
5
```
Example 2
Input
```
1
1 1
```
Expected output
```
0
```
Example 3
Input
```
2
3 4
-1 -1
```
Expected output
```
0
```
Example 4
Input
```
3
0 5
-5 -3
5 -3
```
Expected output
```
1
```
Example 5
Input
```
3
1 1
2 3
5 1
```
Expected output
```
0
```
Example 6
Input
```
6
1 1
-2 3
5 2
-4 1
3 5
-1 2
```
Expected output
```
0
```
Example 7
Input
```
6
3 1
1 3
-3 2
-2 -3
1 -3
4 -1
```
Expected output
```
8
```