P14742 [ICPC 2021 Seoul R] Security System

管理委员会计划引入一个新的安全系统，用于在夜间监控博物馆。博物馆的平面图是一个直边多边形 $P$，其边均为水平或垂直的。此外，$P$ 具有 **$x$ 单调边界**，即 $P$ 与任意垂直线的交要么为空，要么为一条线段。 新安全系统基于红外激光束传感器。一个红外激光束传感器单元沿着放置在 $P$ 内部的一条直线轨道移动，并朝与轨道垂直的方向发射激光束。当检测到任何动静时，会立即发出紧急警报。 轨道表示为水平或垂直的线段。轨道的长度是无限的。对于 $P$ 内的一点 $q$，如果它位于轨道上点 $p$ 处的传感器满足 $q = p$ 或以下条件，则称该点被该传感器监控。 (i) 连接 $p$ 和 $q$ 的线段不接触 $P$ 的外部。 (ii) 轨道与连接 $p$ 和 $q$ 的线段相互正交。 如果一个多边形 $P$ 内的每一点都被轨道集合 $T$ 中某条轨道上的传感器所监控，则称 $P$ 被 $T$ **完全监控**。委员会希望知道完全监控博物馆所需的最少红外激光束传感器单元数量。有两点需要注意：第一，$P$ 的边界（端点除外）不与轨道相交；第二，轨道之间不得相互交叉，即使在端点处也不行。例如，要监控下图所示的 $x$ 单调直边多边形，至少需要 3 个传感器单元。在下图中，蓝线代表轨道。 :::align{center}  ::: 给定一个 $x$ 单调直边多边形，编写一个程序来计算完全监控该多边形所需的最少传感器单元数量。

你的程序需要从标准输入读取数据。输入的第一行包含一个整数 $n$ ($4 \leq n \leq 100,000$)，其中 $n$ 是一个 $x$ 单调直边简单多边形的顶点数。接下来的 $n$ 行按逆时针方向给出各顶点的坐标。每个顶点由两个用单个空格分隔的数字表示，分别是该顶点的 $x$ 坐标和 $y$ 坐标。每个坐标均为介于 $-100,000,000$ 和 $100,000,000$ 之间（含）的整数。

你的程序需要向标准输出写入结果。输出恰好一行。该行应包含一个整数，表示完全监控给定多边形所需的最少传感器单元数量。

翻译由 DeepSeek V3 完成