配点 : 100 点
問題文
2 您将获得 N 积分。i 点的坐标是 (x_i,y_i) 于是,每一天都满足条件。 N 从这一点开始,在若干点上做标记,以满足以下条件。
- 在被标记的点中,相异的 4 点不能构成凸四边形。
请输出作为标记点数量所能考虑的最大值。
凸四边形的定义
在平面上不同的 4 点作为顶点的四边形,如果是凸四边形,需要满足以下所有条件。- 哪个 3 顶点不在同一条直线上。
- 不相邻的 2 边没有共有点。
- 四边形的任意内角都 180 不超过度。
制約
- 所有输入均为整数
- 4 \leq N \leq 500
- |x_i|,|y_i|\leq 10^8
- (x_i,y_i)\neq(x_j,y_j)\ (i\neq j)
入力
输入是按以下格式从标准输入给出的。
N x_1 y_1 x_2 y_2 \vdots x_N y_N
出力
答案 请打印除以 1 行输出。
入力例 1
5 0 0 -1 0 0 -1 1 0 0 1
出力例 1
4
(-1,0) 除了 4 可以在点上做标记。当所有点都做标记时,(0,0) 除了 4 会存在以这些点为顶点的凸四边形,因此不满足条件。
入力例 2
5 0 0 1 1 2 2 2 3 3 2
出力例 2
5
入力例 3
7 -1 8 11 8 -4 -2 19 12 -8 -6 7 6 -1 2
出力例 3
6
入力例 4
4 0 0 2 0 1 -1 0 1
出力例 4
3