题目描述

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

输入格式

• 第一行：一个数 $n$
• 第 $2\sim n+1$ 行：第 $i+1$ 行给出了栅栏点 $i$ 的坐标 $x_i$ 和 $y_i$。

输出格式

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

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

5

数据规模与约定

对于 $45\%$ 的数据，$n\leq 65$。

对于 $100\%$ 的数据，$5 \leq n \leq 250$，$1 \leq x_i \leq 1000$，$1 \leq y_i \leq 1000$

提示

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

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

题目来源

Usaco2008 Dec Gold