Ancient Towers

Time limit7sMemory limit1024 MB

Summary

Count the simple quadrilaterals formed by four of N given points whose area is at least S.

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

Problem

The king of Nlogonia has conquered many lands throughout his life, and now that his son has come of age, the king wants to share his possessions with him.

Nlogonia has $N$ ancient towers that can be seen as points in the Cartesian plane. The king decided that his son must choose four of those towers. Then the son must build a wall connecting the towers, so as to form a (simple but not necessarily convex) quadrilateral with the towers as vertices. The land surrounded by the wall will be owned by the son. The king does not want people making fun of his son for not having enough land, so the area of the quadrilateral must be greater than or equal to a given value $S$ .

The son is eager to choose his portion of the land, but the king wants to know beforehand in how many different ways this can be done. The picture below shows an example with $N = 4$ towers. In this case, there are two different quadrilaterals with an area of at least $S = 2$ .

A quadrilateral is simple if non-contiguous edges do not intersect.

Input

The first line contains two integers $S$ ( $1 \le S \le 10^{18}$ ) and $N$ ( $4 \le N \le 400$ ). Each of the next $N$ lines contains two integers $X$ and $Y$ ( $0 \le X, Y \le 10^{9}$ ), the coordinates of a tower. No two towers have the same location, and no three of them are collinear.

Output

Output a single integer, the number of different simple quadrilaterals that have towers as vertices and an area of at least $S$ . Two quadrilaterals are considered different if they have different vertices or different edges.

Examples4

Example 1
Input
```
2 4
1 2
3 4
3 3
4 1
```
Expected output
```
2
```
Example 2
Input
```
1 4
1 2
3 4
3 3
4 1
```
Expected output
```
3
```
Example 3
Input
```
4 5
1 1
3 3
3 0
0 1
1 0
```
Expected output
```
3
```
Example 4
Input
```
1 4
0 0
1000 0
0 1000
1000 1000
```
Expected output
```
1
```