logo AlgoBeat OnlineJudge
登录 注册

#216282. [ICPC 2023 Jinan R] 近似凸多边形

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

这是一个关于凯文的故事,他是小青鱼的朋友。

凯文是国际凸多边形大赛(ICPC)的裁判长。他为比赛准备了一道几何题。然而,由于他对计算几何不熟悉,他无法为这道题生成正确的凸多边形作为测试数据。

为此凯文很沮丧。他的好朋友小青鱼如此安慰他:“虽然你生成的数据不是凸多边形,但你可以称它为近似凸多边形!”

给定一个由二维平面上的点组成的集合 (包含至少 个点),其中任意两点的坐标都不相同,且任意三个点都不共线。小青鱼称一个多边形 为近似凸多边形,当且仅当:

  • 多边形 是简单多边形,也就是说,多边形的顶点两两不同,且除了相邻边存在公共顶点外,不存在两条边有公共点。
  • 多边形的顶点属于 ,且 中所有点要么在多边形内部,要么在多边形的边界上。

表示所有近似凸多边形构成的集合。可以证明 是一个有限集合,且不是空集合。因此,存在一个多边形 使得 的所有多边形中是最小的( 是多边形 的顶点数量)。

凯文和小青鱼希望您能计算多边形 的数量,满足

输入格式

每个测试文件仅有一组测试数据。

第一行输入一个整数 )表示集合 中点的数量。

对于接下来 行,第 行输入两个整数 )表示集合 中的一个点

保证 中任意两点的坐标都不相同,且任意三个点都不共线。

输出格式

输出一行一个整数表示多边形 的数量。

样例

样例输入 1

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

样例输出 1

9

样例输入 2

5
4 0
0 0
2 1
3 3
3 1

样例输出 2

5

样例输入 3

3
0 0
3 0
0 3

样例输出 3

1

数据范围与提示

对于第一组样例数据,。所有多边形 如下所示。

:::align{center} :::

对于第二组样例数据,。所有多边形 如下所示。

:::align{center} :::