← 返回题目列表

Codeforces · 1220/G

G. 地理定位

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

您在 Gryzzl 公司工作,该公司总部位于印第安纳州波尼。

最近在波尼附近开放了新的国家公园,您将实施地理定位系统,这样人们就不会迷路。您开发的概念是创新且简约的。公园某处将会有 $$$n$$$ 天线。当有人想知道他们当前的位置时,他们的 Gryzzl 全息手机将与天线通信并获取从用户当前位置到所有天线的距离。

知道这些距离和天线位置,应该很容易恢复用户的位置......对吧?嗯,差不多了。唯一的问题是无法区分天线,因此您不知道每个天线对应的距离。您的任务是在给定所有天线位置和无序多组距离的情况下找到用户的位置。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$),它是天线的数量。

以下 $$$n$$$ 行包含天线坐标,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$0 \leq x_i,y_i \leq 10^8$$$)。保证没有两个天线重合。

输入的下一行包含整数 $$$m$$$ ($$$1 \leq n \cdot m \leq 10^5$$$),这是确定用户位置的查询次数。

以下 $$$m$$$ 行包含 $$$n$$$ 个整数 $$$0 \leq d_1 \leq d_2 \leq \dots \leq d_n \leq 2 \cdot 10^{16}$$$。这些整数形成从未知用户位置 $$$(x;y)$$$ 到天线的平方距离的多重集。

对于除示例之外的所有测试用例,保证所有用户位置 $$$(x;y)$$$ 都是随机统一选择的,在具有 $$$0 \leq x, y \leq 10^8$$$ 的所有可能整数位置中彼此独立。

输出

对于每个查询输出 $$$k$$$,匹配给定输入的可能用户位置的数量,然后按字典顺序输出这些位置的列表。

保证所有点上所有 $$$k$$$ 的总和不超过 $$$10^6$$$。

示例

输入 #1

3
0 0
0 1
1 0
1
1 1 2

输出 #1

1 1 1

输入 #2

4
0 0
0 1
1 0
1 1
2
0 1 1 2
2 5 5 8

输出 #2

4 0 0 0 1 1 0 1 1 
4 -1 -1 -1 2 2 -1 2 2

注意

正如您在第二个示例中看到的,尽管最初选择的用户位置具有非负坐标,但您必须输出所有可能的整数位置。