TouchStone
  Please Login
Login Sign Up
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1247
  • Problem
  • P1247最大的栅栏
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    农夫约翰已经购买了n(5≤n≤250)个栅栏柱,来建立一个很完美的栅栏圈,大家都知道最好的栅栏圈是由栅栏柱围成的一个凸多边形,并且栅栏柱越多越完美。牧场被看成为一个平面,栅栏柱看作是平面内的一些整数坐标的点(x_i,y_i)(1<=x_i<=1000,1<=y_i<=1000)。
      现在给你n个栅栏柱,没有任意三点共线,请问你建立一个完美栅栏圈最多要用多少个栅栏柱?

    Input Format

    第一行为一个整数n,第2行到第n+1行每行为两个用空格分开的整数x_i和y_i,表示一个栅栏柱的坐标。

    Output Format

    只有一个整数,表示建造一个完美的栅栏圈需要最多栅栏柱的个数。

    Sample Input

    6
    5 5
    2 3
    3 2
    1 5
    5 1
    1 1

    Sample Output

    5

    Hint

    【样例解释】
      建造一个凸多边形得栅栏圈需要的最多栅栏柱为(2,3), (3,2), (5,1), (5,5), (1,5)
    【数据范围】
      45%的数据n<=65
      100%的数据n<=250