C - Convex Crusher Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

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