P7553 [COCI 2020/2021 #6] Geometrija

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$.

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 one integer on a single line, the number of segments that satisfy the requirement.

#### 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**. | Subtask | Points | Constraints | | :----------: | :----------: | :----------: | | $1$ | $20$ | $3 \le n \le 40$ | | $2$ | $30$ | $3 \le n \le 200$ | | $3$ | $60$ | No additional constraints. | 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](https://hsin.hr/coci/archive/2020_2021/) [CONTEST #6](https://hsin.hr/coci/archive/2020_2021/contest6_tasks.pdf) _T4 Geometrija_**。 Translated by ChatGPT 5