306608: CF1220G. Geolocation
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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