P16320 [ICPC 2023 Jinan R] 近似凸多边形

这是一个关于凯文的故事，他是小青鱼的朋友。 凯文是国际凸多边形大赛（ICPC）的裁判长。他为比赛准备了一道几何题。然而，由于他对计算几何不熟悉，他无法为这道题生成正确的凸多边形作为测试数据。 为此凯文很沮丧。他的好朋友小青鱼如此安慰他：“虽然你生成的数据不是凸多边形，但你可以称它为近似凸多边形！” 给定一个由二维平面上的点组成的集合 $S$（包含至少 $3$ 个点），其中任意两点的坐标都不相同，且任意三个点都不共线。小青鱼称一个多边形 $P$ 为近似凸多边形，当且仅当： - 多边形 $P$ 是简单多边形，也就是说，多边形的顶点两两不同，且除了相邻边存在公共顶点外，不存在两条边有公共点。 - 多边形的顶点属于 $S$，且 $S$ 中所有点要么在多边形内部，要么在多边形的边界上。 令 $\mathbb{U}$ 表示所有近似凸多边形构成的集合。可以证明 $\mathbb{U}$ 是一个有限集合，且不是空集合。因此，存在一个多边形 $R$ 使得 $|R|$ 在 $\mathbb{U}$ 的所有多边形中是最小的（$|R|$ 是多边形 $R$ 的顶点数量）。 凯文和小青鱼希望您能计算多边形 $Q \in \mathbb{U}$ 的数量，满足 $|Q| \le |R| + 1$。

每个测试文件仅有一组测试数据。 第一行输入一个整数 $n$（$3 \le n \le 2 \times 10^3$）表示集合 $S$ 中点的数量。 对于接下来 $n$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $y_i$（$-10^6 \le x_i, y_i \le 10^6$）表示集合 $S$ 中的一个点 $(x_i, y_i)$。 保证 $S$ 中任意两点的坐标都不相同，且任意三个点都不共线。

输出一行一个整数表示多边形 $Q$ 的数量。

对于第一组样例数据，$|R| = 4$。所有多边形 $Q$ 如下所示。 :::align{center}  ::: 对于第二组样例数据，$|R| = 3$。所有多边形 $Q$ 如下所示。 :::align{center}  :::