POLYGON-动态规划-中高级

 1 Sec 64 MB |  显示标签
3559
通过提交

题目描述

对于一个多边形来说,在该多边形内任取两点,如果这两点连成的线段落在多边形内,则称这样的多边形为凸多边形。
平面上有N个坐标值为自然数的圆点。顶点数最多凸多边形是指由给定的圆点中的一部分组成的凸多边形,它包含最大可能的顶点数。原点,即坐标内中心(0,0)必须是顶点数最多凸多边形的一个顶点。
编写程序求出这样的凸多边形的最大顶点数。注意一个多边形的连续的边不能是平行的。

输入格式

输入文件的第一行包含一个自然数N,2≤N≤100,表示给定的圆点数。
下面的N行每行包含两个用空格隔开的自然数X和Y,1≤X≤100,1≤Y≤100,表示一个圆点的坐标值。所有的圆点是不相同的。

输出格式

输出文件的第一行也是唯一的一行应该包含顶点数最多凸多边形的顶点数。注意结果应不小于3。

样例输入 #1

8
10 8
3 9
2 8
2 3
9 2
9 10
10 3
8 10

样例输出 #1

8

提示

LIS

 上传者
coach
 创建时间
2012-11-13 12:22