← 返回题目列表

AtCoder · utpc2025_c

C. 凸破碎机

中文机器翻译题面 查看原题

配点 : 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