← 返回题目列表

Codeforces · 958/A3

A3. 死星(硬)

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

恒星日期是 2015 年,死星比以往任何时候都更大!这一次,两名叛军间谍再次给了海蒂两张地图,上面标有死星的可能位置。

海蒂现在收到了两张地图,上面有 N 个死星的可能位置。她知道每张地图都可能已损坏,并且可能包含一些不是死星的恒星。此外,每张地图都是从不同的角度创建的。因此,其中一张地图中显示的星星相对于另一张地图旋转和平移。现在海蒂想找出两张地图上显示的星星中哪些实际上是死星,以及两张地图上死星之间的对应关系。

输入

输入的第一行包含一个整数 N (1000 ≤ N ≤ 50000) – 死星的数量。输入的第二行包含一个整数 N1 (N ≤ N1 ≤ 1.5·N) – 第一个地图中的星星数量。接下来的 N1 行指定第一张地图中星星的坐标。第 i 行包含两个空格分隔的浮点数 xi 和 yi,每个精度为两位十进制小数,表示第一张地图中第 i 个恒星的坐标。

输入的下一行包含一个整数 N2 (N ≤ N2 ≤ 1.5·N) – 第二张地图中的星星数量。接下来的 N2 行包含第二张地图中星星的位置,以与第一张地图相同的格式给出。

输出

您应该输出正好 N 行,每行包含一对以空格分隔的整数 i1 和 i2。每条这样的线应指示第一个地图中编号为 i1 的恒星对应于第二个地图中编号为 i2 的恒星。如果输出中列出的不同对中超过 90% 确实正确,则您的答案将被视为正确。

注意

测试通过以下方式生成:

- 死星 N 的数量以某种方式预先选择。
- 第一张和第二张地图上的星星数量 N1 和 N2 在 1.0 × N 和 1.5 × N 之间均匀随机选择。
- N颗死星是随机生成的,坐标在 - 10000到10000之间。
- 第一张和第二张地图的额外 N1 - N 和 N2 - N 星星分别以相同的方式生成。
- 生成平移向量 (dx, dy),dx 和 dy 在  - 10000 到 10000 之间随机均匀选择。第一个地图中的每个点都由 (dx, dy) 平移。
- 生成旋转角度 θ,θ 在 0 到 2π 之间随机均匀选择。第一张图中的每个点绕原点旋转 θ 角度。
- 第二张地图的平移和旋转以相同的方式生成和应用。
- 两张地图的点顺序是随机排列的。
- 保存测试用例,每个点都以两位小数精度写入。