题目描述

:::align{center}

大小为 4 的 Voronoi 图。 :::

在二维笛卡尔坐标系中，我们定义非空点集 $S$ 的 Voronoi 图 为一种按照“该位置距离集合 $S$ 中哪个点最近？”这一准则划分平面的图。更精确地说，给定非空点集 $\{P_1, P_2, \cdots, P_n\}$ 的 Voronoi 图是一个 区域 的集合：点 $K$ 属于区域 $i$，当且仅当对于所有 $1 \le j \le n$，都有 $d(P_i, K) \le d(P_j, K)$ 成立。与通常的 Voronoi 图不同，本题中我们使用曼哈顿距离。$d(X, Y)$ 表示点 $X$ 和 $Y$ 之间的 曼哈顿 距离。两点之间的曼哈顿距离是它们笛卡尔坐标的绝对差之和。

例如，在上图中，平面上的每个位置都根据距离该位置最近的点进行了着色。属于单个区域的点用表示该区域的浅色着色，而属于多个区域的点则形成黑色的线和点。

我们想要找出 Voronoi 图中无界区域的数量。一个区域是无界的，如果对于任意实数 $R$，都存在该区域中的点 $P$，使得 $d(O, P) > R$，其中 $O$ 是原点。

输入格式

第一行给出构成 Voronoi 图的点的数量 $n$。 ($1 \le n \le 200\ 000$)

接下来 $n$ 行中的第 $i$ 行，给出两个整数，表示 $P_i$ 的 $x$ 和 $y$ 坐标。这些是构成 Voronoi 图的点。所有 $n$ 个点互不相同。 ($|x|, |y| \le 10^9$)

输出格式

输出仅包含一行，该行包含一个整数。这应是 Voronoi 图中无界区域的数量。

4
0 0
-4 0
3 4
4 -2

4

5
1 1
2 2
3 3
4 4
5 5

5

9
-4 -4
-4 0
-4 4
0 -4
0 0
0 4
4 -4
4 0
4 4

8

提示

翻译由 DeepSeek 完成