Geolocation

题意翻译

**题目描述** 你在 Gryzzl 公司工作，总部设在印第安纳州波尼。 波尼附近新建的的国家公园最近开放了，你要实现地理定位系统，这样人们就不会迷路了。你是创新和极简主义者，提出的概念自然也是如此。公园里有$n$个天线，当有人想知道他们当前的位置，他们的 Gryzzl 全息手机将与天线通信，并获得从用户当前位置到所有天线的距离。 知道这些距离和天线位置应该很容易恢复用户的位置，对吗？好吧，是这样。不过唯一的问题是没有办法区分天线，所以你不知道，哪个距离对应于每个天线。你的任务是只要给出所有天线的位置和一个无序的距离集合，就可以找到一个用户的位置。 **输入格式** 第一行包含一个整数$n(2\le n\le 10^5)$，表示公园里的天线数量。 接下来的$n$行，每行包含两个整数$x_i$，$y_i$（$0\le x_i,y_i\le 10^8$），表示第$i$根天线的坐标。数据保证每根天线的坐标各不相同。 下一行包含一个整数$m$（$1\le n\ ⋅m\le 10^5$），表示需要查询位置的用户数量。 接下来$m$行，每行包含$n$个整数$0\le d_1\le d_2\le ⋯\le d_n\le 2\ ⋅10^{16}$，这些整数构成从需要查询位置的用户位置$(x$；$y)$到天线的平方距离的集合。 测试数据保证所有用户位置（$x$；$y$）都是随机生成的，在所有可能整数位置中彼此独立。 **输出格式** 对于每个查询输出$k$，表示可能的用户位置的数量，然后再以字典序依次输出这些位置。 **说明** 虽然最初的用户位置为非负坐标，但您必须输出所有可能的整数位置，换句话说，用户位置坐标可能会是负数。

题目描述

You are working for the Gryzzl company, headquartered in Pawnee, Indiana. The new national park has been opened near Pawnee recently and you are to implement a geolocation system, so people won't get lost. The concept you developed is innovative and minimalistic. There will be $ n $ antennas located somewhere in the park. When someone would like to know their current location, their Gryzzl hologram phone will communicate with antennas and obtain distances from a user's current location to all antennas. Knowing those distances and antennas locations it should be easy to recover a user's location... Right? Well, almost. The only issue is that there is no way to distinguish antennas, so you don't know, which distance corresponds to each antenna. Your task is to find a user's location given as little as all antennas location and an unordered multiset of distances.

输入输出格式

输入格式

The first line of input contains a single integer $ n $ ( $ 2 \leq n \leq 10^5 $ ) which is the number of antennas. The following $ n $ lines contain coordinates of antennas, $ i $ -th line contain two integers $ x_i $ and $ y_i $ ( $ 0 \leq x_i,y_i \leq 10^8 $ ). It is guaranteed that no two antennas coincide. The next line of input contains integer $ m $ ( $ 1 \leq n \cdot m \leq 10^5 $ ), which is the number of queries to determine the location of the user. Following $ m $ lines contain $ n $ integers $ 0 \leq d_1 \leq d_2 \leq \dots \leq d_n \leq 2 \cdot 10^{16} $ each. These integers form a multiset of squared distances from unknown user's location $ (x;y) $ to antennas. For all test cases except the examples it is guaranteed that all user's locations $ (x;y) $ were chosen uniformly at random, independently from each other among all possible integer locations having $ 0 \leq x, y \leq 10^8 $ .

输出格式

For each query output $ k $ , the number of possible a user's locations matching the given input and then output the list of these locations in lexicographic order. It is guaranteed that the sum of all $ k $ over all points does not exceed $ 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 

说明

As you see in the second example, although initially a user's location is picked to have non-negative coordinates, you have to output all possible integer locations.