P1247最大的栅栏 | |
|
问题描述
农夫约翰已经购买了n(5≤n≤250)个栅栏柱,来建立一个很完美的栅栏圈,大家都知道最好的栅栏圈是由栅栏柱围成的一个凸多边形,并且栅栏柱越多越完美。牧场被看成为一个平面,栅栏柱看作是平面内的一些整数坐标的点(x_i,y_i)(1<=x_i<=1000,1<=y_i<=1000)。
现在给你n个栅栏柱,没有任意三点共线,请问你建立一个完美栅栏圈最多要用多少个栅栏柱?
输入格式
第一行为一个整数n,第2行到第n+1行每行为两个用空格分开的整数x_i和y_i,表示一个栅栏柱的坐标。
输出格式
只有一个整数,表示建造一个完美的栅栏圈需要最多栅栏柱的个数。
样例输入
6
5 5
2 3
3 2
1 5
5 1
1 1
样例输出
5
提示
【样例解释】
建造一个凸多边形得栅栏圈需要的最多栅栏柱为(2,3), (3,2), (5,1), (5,5), (1,5)
【数据范围】
45%的数据n<=65
100%的数据n<=250