← 返回题目列表

AtCoder · icpc2014spring_f

F. 多边形守卫

中文机器翻译题面 查看原题

问题陈述

您是Polygon国国防部的IT系统管理员。

多边形国家的边界​​形成具有 $N$ 个顶点的多边形。在 2D 平面上绘制时,其所有顶点均位于晶格点处,且所有边均与 $x$ 轴或 $y$ 轴平行。

为了防止敌人入侵该国,它的边境周围有非常坚固的防御墙。然而,在顶点、墙体的连接处存在不可避免的结构弱点。因此,敌人可能会从顶点攻击和入侵。

为了观察顶点并尽快发现敌人的入侵,魔法部决定雇佣一些守卫。 该部计划将它们放置在一些顶点,以便至少一名警卫观察所有顶点。 如果连接 $A$ 和 $B$ 的整个线段位于多边形国家的内部或边缘,则顶点 $A$ 处的守卫可以观察顶点 $B$。 当然,守卫可以观察他们所在的顶点。守卫可以同时观察他或她可以观察到的所有顶点。

为了减少国防开支,国防部希望尽量减少警卫人数。 你的任务是计算观察多边形国家所有顶点所需的最少守卫数量。


输入

输入的格式如下。

$N$
$X_1$ $Y_1$
:
:
$X_N$ $Y_N$

第一行包含偶数 $N$ ($4 \le N \lt 40$)。 以下 $N$ 行描述了 Polygon Country 的顶点。 每行包含两个整数 $X_i$ 和 $Y_i$ ($1 \le i \le N$, $\lvert X_i \rvert \le 1{,}000$, $\lvert Y_i \rvert \le 1{,}000$),用一个空格分隔。 第 $i$ 个顶点的位置是 $(X_i,Y_i)$。

如果 $i$ 为奇数,则 $X_i = X_{i+1}$, $Y_i \ne Y_{i+1}$。否则,$X_i \ne X_{i+1}$,$Y_i = Y_{i+1}$。这里,我们认为$X_{N+1} = X_1$,$Y_{N+1} = Y_1$。 在 $x$ 轴向右、$y$ 轴向上的坐标系下,顶点按逆时针顺序给出。 多边形国家的形状很简单。也就是说,每条边不与其他边共享任何点,除了其两个端点与其相邻边共享之外。

输出

打印一行中最少的守卫数量。


示例输入 1

8
0 2
0 0
2 0
2 1
3 1
3 3
1 3
1 2

样本输入 1 的输出

1

示例输入 2

12
0 0
0 -13
3 -13
3 -10
10 -10
10 10
-1 10
-1 13
-4 13
-4 10
-10 10
-10 0

样本输入 2 的输出

2