CF936E Iqea

Gridland 位于一个无限大的网格上，由若干个格子组成。Gridland 的每个格子都是一座城市。相邻格子上的两座城市之间有一条长度为 $1$ 的道路。可以通过道路从任意一座城市到达另一座城市。两座城市之间的距离定义为从一座城市到另一座城市的最短路径上道路的总长度。 此外，从不属于 Gridland 的任意一个格子出发，只经过不属于 Gridland 的格子，也可以到达其它所有不属于 Gridland 的格子。换句话说，Gridland 是连通的，Gridland 的补集也是连通的。 目前 Gridland 的所有城市都没有 Iqea 著名商店。但 Iqea 计划在 Gridland 内开设商店。为了方便顾客，Iqea 决定开发一个应用程序。通过该应用，用户可以查询距离最近的 Iqea 商店的距离。你的任务就是开发这个应用。 你需要处理两种操作： - 在坐标为 $(x, y)$ 的城市新开了一家 Iqea 商店； - 顾客想知道他所在城市（坐标为 $(x, y)$）距离最近的已开业 Iqea 商店的距离。 注意，顾客只能通过道路移动，且在前往商店的途中不能离开 Gridland。

第一行包含一个整数 $n$，表示 Gridland 中城市的数量（$1 \leq n \leq 300000$）。接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个城市所在格子的坐标（$1 \leq x_i, y_i \leq 300000$）。任意两个城市的坐标均不相同。所有城市组成一个连通区域，且其补集也是连通的。 接下来一行包含一个整数 $q$，表示操作的数量（$0 \leq q \leq 300000$）。接下来的 $q$ 行，每行包含三个整数 $t_i$、$x_i$ 和 $y_i$（$t_i \in \{1, 2\}$，$1 \leq x_i, y_i \leq 300000$）。如果 $t_i = 1$，表示在坐标为 $(x_i, y_i)$ 的城市新开了一家 Iqea 商店。保证该城市之前没有商店。如果 $t_i = 2$，表示需要查询坐标为 $(x_i, y_i)$ 的城市距离最近的已开业 Iqea 商店的最小距离。保证所有操作中的 $(x_i, y_i)$ 都属于 Gridland。

对于每个类型为 2 的操作，输出一个整数，表示距离最近的 Iqea 商店的最小距离。如果尚未有任何商店开业，输出 $-1$。

由 ChatGPT 4.1 翻译