Arrow Collector

Time limit4sMemory limit512 MB

Summary

Count the ordered tuples (A, B, C, D) of points that form an upper-left arrow, where C and D lie in the 90-degree cone at A and are closer to A than B.

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

Problem

Dong-hyeon is an arrow collector who gathers arrows. Lately he is very excited because he recently found an arrow mine with as many as $N$ points. All $N$ points are distinct, and no three points lie on one line.

To mine arrows from the mine, one must pick four different points among the $N$ points and connect them. There are several ways to connect four points into an arrow, but the most valuable one is ↖️, named arrow_upper_left. ↖️ is defined as an ordered tuple $(A, B, C, D)$ of four distinct points that satisfies the following conditions.

The $x$ coordinate of $A$ is less than that of $B$ , and the $y$ coordinate of $A$ is greater than that of $B$ .
Seen from $A$ , $C$ is located clockwise from $B$ by more than 0 and less than 90 degrees.
Seen from $A$ , $D$ is located counterclockwise from $B$ by more than 0 and less than 90 degrees.
Both segments $AC$ and $AD$ are shorter than segment $AB$ .

Dong-hyeon wants to mine every kind of ↖️ in this mine, but first he wants to know how many distinct ↖️ exist. Two ↖️ are different if their ordered four-point tuples differ. Count them for him.

Input

The first line contains $N$ , the number of points in the arrow mine. The next $N$ lines each contain two integers $x_i$ and $y_i$ , separated by a space, giving the coordinates of a point.

Output

Print the number of distinct ↖️ in the arrow mine.

Constraints

$4 \le N \le 3\,000$
$-10^9 \le x_i, y_i \le 10^9$
All points are distinct, and no three points lie on one line.

Examples1

Example 1
Input
```
6
1 6
3 5
3 9
6 7
7 1
9 6
```
Expected output
```
6
```