P16320 [ICPC 2023 Jinan R] Approximate Convex Polygon.

This is a story about Kevin, who is a friend of Xiaoqingyu. Kevin is the chief judge of the International Convex Polygon Contest (ICPC). He prepared a geometry problem for the contest. However, because he is not familiar with computational geometry, he cannot generate correct convex polygons as the testdata for this problem. So Kevin feels upset. His good friend Xiaoqingyu comforts him like this: “Although the data you generate are not convex polygons, you can call them approximate convex polygons!” You are given a set $S$ of points on the 2D plane (containing at least $3$ points). The coordinates of any two points are different, and no three points are collinear. Xiaoqingyu calls a polygon $P$ an approximate convex polygon if and only if: - Polygon $P$ is a simple polygon. That is, all vertices of the polygon are pairwise distinct, and no two edges share any common point except that adjacent edges share a common endpoint. - The vertices of the polygon belong to $S$, and every point in $S$ is either inside the polygon or on the boundary of the polygon. Let $\mathbb{U}$ be the set of all approximate convex polygons. It can be proven that $\mathbb{U}$ is finite and non-empty. Therefore, there exists a polygon $R$ such that $|R|$ is the minimum among all polygons in $\mathbb{U}$ (where $|R|$ is the number of vertices of polygon $R$). Kevin and Xiaoqingyu want you to compute the number of polygons $Q \in \mathbb{U}$ satisfying $|Q| \le |R| + 1$.

Each test file contains only one test case. The first line contains an integer $n$ ($3 \le n \le 2 \times 10^3$), denoting the number of points in set $S$. For the next $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($-10^6 \le x_i, y_i \le 10^6$), denoting a point $(x_i, y_i)$ in set $S$. It is guaranteed that the coordinates of any two points in $S$ are different, and no three points are collinear.

Output one line with one integer, denoting the number of polygons $Q$.

For the first sample, $|R| = 4$. All polygons $Q$ are shown below. :::align{center}  ::: For the second sample, $|R| = 3$. All polygons $Q$ are shown below. :::align{center}  ::: Translated by ChatGPT 5