#P18003. Convex Crusher

Convex Crusher

Convex Crusher

平面上有 NN 个互不相同的点,第 ii 个点的坐标为 (xi,yi)(x_i,y_i)。请选出尽可能多的点,使选出的点中不存在四个点作为顶点构成凸四边形。

这里的凸四边形要求:四个顶点互不相同,任意三个顶点不共线,非相邻边没有公共点,且每个内角都严格小于 180∘180^\circ。因此含三个共线点的退化四边形不算凸四边形。

输入格式

第一行一个整数 NN。接下来 NN 行,每行两个整数 xi,yix_i,y_i。

输出格式

输出最多能选出的点数。

数据范围

4≤N≤5004\le N\le500,∣xi∣,∣yi∣≤108|x_i|,|y_i|\le10^8,任意两个输入点的坐标不同。

样例 1

输入

5
0 0
-1 0
0 -1
1 0
0 1

输出

4

样例 2

输入

5
0 0
1 1
2 2
2 3
3 2

输出

5

样例 3

输入

7
-1 8
11 8
-4 -2
19 12
-8 -6
7 6
-1 2

输出

6

样例 4

输入

4
0 0
2 0
1 -1
0 1

输出

3