AT_utpc2025_c.Convex Crusher

在二维平面上给出 $N$ 个点，第 $i$ 个点的坐标为 $(x_i, y_i)$。请从这 $N$ 个点中标记若干个点，要求满足以下条件：

• 标记的点中，不存在任意 $4$ 个互不相同的点能组成一个凸四边形。

请输出满足条件的最多可标记点的数量。

凸四边形的定义：设有平面上 $4$ 个互不相同的点为顶点的四边形，当且仅当以下条件全部满足时，该四边形为凸四边形：

• 任意三个顶点不共线。
• 相邻的两条边之外，其余两边没有交点。
• 四边形的每个内角都小于 $180$ 度。

输入通过标准输入按以下格式给出。

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

请输出答案一行。

样例解释 1

可以标记除 $(-1,0)$ 以外的 $4$ 个点。如果将所有点都标记，那么除 $(0,0)$ 外的 $4$ 个点将能组成一个凸四边形，因此不满足条件。

数据范围

• 输入均为整数。
• $4 \leq N \leq 500$。
• $|x_i|, |y_i| \leq 10^8$。
• $(x_i, y_i) \neq (x_j, y_j)\ (i \neq j)$。

由 ChatGPT 5 翻译