logo AlgoBeat OnlineJudge
登录 注册

#101591. [BZOJ 1591] [Usaco2008 Dec]Largest Fence 最大的围栏

内存限制:64 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

FJ 有 个栅栏点,他需要围成一个栅栏圈,这个圈是一个凸包并且凸包上的点最多。

输入格式

  • 第一行:一个数
  • 行:第 行给出了栅栏点 的坐标

输出格式

  • 第一行:一个数,表示凸包上可能点数的最大值。

样例

样例输入 #1

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

样例输出 #1

5

数据范围与提示

对于 的数据,

对于 的数据,

样例输入为一个正方形和其内部的两个点。

样例中含点数最多的凸包上含的点如下:

Usaco2008 Dec Gold