Description

There are $n$ non-collinear points on a plane. If two line segments $\overline{AB}$ and $\overline{CD}$ have a common point other than $A, B, C, D$, then they are said to “intersect”.

Let $S$ be the set of all line segments obtained by connecting every pair of the $n$ points. Find the number of segments that do not intersect any other segment in $S$.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th point.

Output Format

Output one integer on a single line, the number of segments that satisfy the requirement.

4
1 1
-1 1
-1 -1
1 -1

4

4
-1 -1
1 -1
0 1
0 0

6

Hint

Explanation for Sample 1

The segments that satisfy the requirement are shown in the figure:

Explanation for Sample 2

The segments that satisfy the requirement are shown in the figure:

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $3 \le n \le 10^3$, $-10^9 \le x_i, y_i \le 10^9$.

Notes

The score of this problem follows the original COCI setting, with a full score of $110$.

Translated from COCI2020-2021 CONTEST #6 T4 Geometrija。

Translated by ChatGPT 5