P17040 [NWERC 2021] 戴森环 / Dyson Circle

译自 [Northwestern Europe Regional Contest (NWERC) 2021](http://2021.nwerc.eu) Problem D。 原题许可协议为 CC BY-SA。

戴森球是一种围绕太阳或其他恒星建造的理论结构，可以捕获该恒星输出的全部能量。科幻作家曾设想，随着先进文明的能量需求不断无限增长，它们最终会建造这样的球体。在我们的三维空间中，戴森球仍然属于幻想。不过，你的维度邻居所在的二维世界 Flatland 中，主要能源公司 **Dy & Son** 委托你进行一项可行性研究。 **Dy & Son** 开发了一种模块化戴森环。它由独立的正方形戴森单元组成，这些单元可以连接成一个封闭环来收集能量。你的任务是弄清楚，为了包围它们感兴趣的一颗或多颗恒星，实际需要多少个这样的戴森单元。注意，它们想要的是一个单独的戴森环，而不是每颗恒星各一个。 为了方便起见，**Dy & Son** 想要包围的恒星以及所使用的戴森单元都被建模为边长恰好为 $1$ 的正方形，单位为 **Intergalactic Unit**，并且与 **Intergalactic Coordinate System** 对齐。如果两个戴森单元至少有一个角相同，则认为它们相连。样例输入 #1 的示意见下图。 :::align{center}  ::: 图示：样例输入 #1 中的四颗恒星（黄色正方形）以及一个围住它们的最优戴森环（蓝色虚线正方形），白色部分表示剩余的太空黑暗区域。 形式化地说，你需要在平面中选择一些正方形，将它们变成戴森单元，使得剩余的正方形可以被划分为 **内部** 正方形和 **外部** 正方形。所有恒星都必须位于内部正方形中。内部正方形必须形成一个通过边连通的区域，并且不能通过边与外部正方形连通。外部正方形形成一个连通区域，并一直延伸到无穷远处。

输入包含： - 一行一个整数 $n$（$1 \leq n \leq 2\cdot 10^5$），表示恒星数量。 - 接下来 $n$ 行，每行包含两个整数 $x$ 和 $y$（$-10^6 \leq x,y \leq 10^6$），表示一颗恒星中心的位置。 任意两颗恒星的位置不同。

输出捕获输入中所有恒星能量所需的最少戴森单元数量。

【数据规模与约定】 对于所有数据，$1 \leq n \leq 2\cdot 10^5$；每颗恒星中心坐标满足 $-10^6 \leq x,y \leq 10^6$；任意两颗恒星位置不同。