提示: 欢迎访问OurACM平台。
Problem 1485 牧场

Accept: 48    Submit: 163
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

阿甘在无聊的时候买下了个牧场。牧场肯定有围栏,阿甘要做的事很奇怪,简单说来就是这样:

平面上有N个坐标值为自然数的点。顶点数最多凸多边形是指由给定的点中的一部分组成的凸多边形,它包含最大可能的顶点数。原点,即坐标内中心(0,0)必须是顶点数最多凸多边形的一个顶点。

编写程序求出这样的凸多边形的最大顶点数。注意一个多边形的连续的边不能是平行的。

Ps:对于一个多边形来说,在该多边形内任取两点,如果这两点连成的线段落在多边形内,则称这样的多边形为凸多边形。

Input

本题有多组输入数据,你必须处理到EOF为止

输入文件的第一行包含一个自然数N,2≤N≤100,表示给定的点数。

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

Output

输出数据的包含顶点数最多凸多边形的顶点数。注意结果应不小于3。

Sample Input

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

Sample Output

8

Source

FOJ月赛-2007年4月

Submit  Back  Status  Discuss