TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1247
  • 题目
  • P1247最大的栅栏
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    农夫约翰已经购买了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