#P1591. [Usaco2008 Dec]Largest Fence 最大的围栏

[Usaco2008 Dec]Largest Fence 最大的围栏

题目描述

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

输入格式

  • 第一行:一个数 nn
  • 第 2∼n+12\sim n+1 行:第 i+1i+1 行给出了栅栏点 ii 的坐标 xix_i 和 yiy_i。

输出格式

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

数据规模与约定

对于 45%45\% 的数据,n≤65n\leq 65。

对于 100%100\% 的数据,5≤n≤2505 \leq n \leq 250,1≤xi≤10001 \leq x_i \leq 1000,1≤yi≤10001 \leq y_i \leq 1000

提示

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

样例中含点数最多的凸包上含的点如下:(2,3) (2 , 3) ,(3,2) (3 , 2) ,(5,1) (5 ,1) ,(5,5) (5 , 5) ,(1,5) (1 , 5)

题目来源

Usaco2008 Dec Gold

保证所有栅栏点坐标互不相同,且不存在三点共线。