#P18003. Convex Crusher
Convex Crusher
Convex Crusher
平面上有 个互不相同的点,第 个点的坐标为 。请选出尽可能多的点,使选出的点中不存在四个点作为顶点构成凸四边形。
这里的凸四边形要求:四个顶点互不相同,任意三个顶点不共线,非相邻边没有公共点,且每个内角都严格小于 。因此含三个共线点的退化四边形不算凸四边形。
输入格式
第一行一个整数 。接下来 行,每行两个整数 。
输出格式
输出最多能选出的点数。
数据范围
,,任意两个输入点的坐标不同。
样例 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