The Jade Mask

Interview

Time limit1sMemory limit1024 MB

Summary

Given N points with no three collinear, count the four-point subsets that form a convex quadrilateral.

Level: Medium4 of 10
Topics: Geometry, Brute force, Math
Solved: No attempts yet

Problem

A large mountain behind the village is home to a single goblin. The goblin covers its frightening face with a mask and goes to the village festival. This year the goblin enjoyed the festival, and now it wants to hide its precious masks for the next one. There are $4$ masks, and it will hide them in four different caves among the $N$ caves on the mountain.

Each cave's location can be represented as a point on the coordinate plane. The goblin likes geometry and wants the four caves that hold the masks to form a convex quadrilateral when connected in a suitable order. In this problem, a convex quadrilateral is a quadrilateral whose four sides meet only at the vertices and whose interior angles are all less than 180°.

Curious about the answer, the goblin wonders how many convex quadrilaterals can be formed using four different caves as vertices. Given the coordinates of $N$ caves, write a program that answers this question.

Input

The first line contains the number of caves $N$ .

Each of the next $N$ lines contains the $x$ and $y$ coordinates of a cave, separated by a space.

Output

Print the number of convex quadrilaterals that can be formed using four different caves as vertices.

Constraints

$4\le N\le 50$
All given $x$ and $y$ coordinates are integers whose absolute values are at most $10^5$ .
The same point is not given more than once.
No three points lie on a single line.

Examples2

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