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 翻译