TouchStone
  Please Login
ログイン 登録
距离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