Triangles

Time limit1.2sMemory limit1024 MB

Summary

Count triangles formed by n points, no three collinear, that contain at least one other point strictly inside.

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

Problem

A triangle is a simple polygon having exactly three distinct corners that are not collinear. For any set $S$ of points in the plane, a triangle is said to have a conflict with $S$ if there is at least one point contained both in $S$ and in the interior of the triangle, excluding its boundary, simultaneously.

Now, the set $S$ is given to be a set of $n$ points in the plane, no three of which are collinear, and let $T$ be the set of all triangles whose corners are chosen from the set $S$ . How many of those in $T$ have a conflict with $S$ ?

Write a program that outputs the number of triangles in $T$ that have a conflict with $S$ .

Input

Your program is to read from standard input. The input starts with a line containing an integer $n$ ( $3 \le n \le 500$ ), where $n$ is the number of points in the set $S$ . Each of the following $n$ lines consists of two integers, each between $-10^6$ and $10^6$ , representing the coordinates of each point in the set $S$ . It is guaranteed that no three points in the set $S$ are collinear.

Output

Your program is to write to standard output. Print exactly one line. The line should contain an integer that represents the number of triangles whose corners are chosen from the set $S$ and that have a conflict with the set $S$ .

Examples2

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