← 返回题目列表

Codeforces · 936/E

E. 宜凯

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

Gridland 放置在无限网格上,具有由单元组成的图形形状。 Gridland 的每个单元格都是一座城市。位于相邻单元格中的两个城市通过长度为 $$$1$$$ 的道路连接起来。可以通过道路从任何城市前往任何其他城市。的 距离 两个城市之间的道路是从一个城市到另一个城市的最小道路总长度。通过仅使用不属于 Gridland 的单元格,可以从任何不属于 Gridland 的单元格获取不属于 Gridland 的任何其他单元格。换句话说,Gridland 是连通的,Gridland 的补充也是连通的。

目前Gridland没有哪个城市有Iqea名店。但 Iqea 制定了在 Gridland 开设商店的宏伟计划。为了方便客户,Iqea 决定开发一个应用程序。使用此应用程序,每个人都可以了解到最近的 Iqea 的距离。您将开发此应用程序。

您需要处理两种类型的查询:

  • 新的 Iqea 商店已在城市开业,坐标为 $$$(x, y)$$$;
  • 客户想知道距离他的城市最近的已开业 Iqea 商店的距离,该商店位于坐标为 $$$(x, y)$$$ 的单元格中。

请注意,顾客只能通过道路移动,并且在前往商店的途中永远不能离开 Gridland。

输入

第一行包含一个整数 $$$n$$$ — Gridland 中的城市数量 ($$$1 \le n \le 300\,000$$$)。以下 $$$n$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ — 包含第 $$$i$$$ 城市的像元坐标 ($$$1 \le x_i, y_i \le 300\,000$$$)。没有两个细胞重合。细胞形成连通区域,该区域的补体也是连通的。

以下行包含单个整数 $$$q$$$ — 查询数 ($$$0 \le q \le 300\,000$$$)。以下 $$$q$$$ 行包含查询,第 $$$i$$$ 行由三个整数 $$$t_i$$$、$$$x_i$$$ 和 $$$y_i$$$ 组成($$$t_i \in \{1, 2\}$$$, $$$1 \le x_i, y_i \le 300\,000$$$)。如果 $$$t_i = 1$$$,则表示坐标为 $$$(x_i, y_i)$$$ 的城市已开设新的 Iqea 商店。可以肯定的是,这个城市以前没有Iqea店。如果 $$$t_i = 2$$$,您需要找到从坐标为 $$$(x_i, y_i)$$$ 的城市到最近的已开业 Iqea 商店的距离。保证在两种类型的查询中单元格 $$$(x_i, y_i)$$$ 属于 Gridland。

输出

对于第二类型的每个查询,输出单个整数 - 到最近的 Iqea 商店的最小距离。如果尚未开设 Iqea 商店,则输出 $$$-1$$$。

示例

输入
复制

7
1 2
1 3
2 3
3 1
3 2
3 3
4 2
5
2 3 2
1 4 2
2 1 2
1 3 3
2 2 3

输出
复制

-1
5
1

输入
复制

6
1 1
1 2
1 3
2 1
2 2
3 1
4
1 3 1
2 1 2
1 2 2
2 1 3

输出
复制

3
2

第一个例子的解释:

在所有查询之前

第一次查询

第二次查询

第三次查询

第四次查询

第五查询

第二个例子的解释:

在所有查询之前

第一次查询

第二次查询

第三次查询

第四次查询