CF958A3 Death Stars (hard)

公元 2015 年，死星变得比以往更庞大！这回，海蒂从两个反抗军间谍那里收到了两份可能包含死星位置的地图。 海蒂现有两张地图，每张都标示了 $N$ 个可能是死星的位置。她知道这两张地图可能存在错误，可能标记了一些并非死星的星星。而且，由于两张地图是从不同视角画出的，每颗星在其中一张地图上的位置与另一张地图相比，发生了旋转和平移。为了确定哪些星星是真正的死星，并找出它们在两个地图上的对应关系，海蒂需要你的帮助。

第一行是一个整数 $N$（$1000 \le N \le 50000$），表示死星的数量。第二行是一个整数 $N_1$（$N \le N_1 \le 1.5 \times N$），表示第一张地图上的总星星数。接下来的 $N_1$ 行，每行有两个用空格分隔的浮点数 $x_i$ 和 $y_i$，表示第一张地图上每颗星星的坐标，数值都精确到小数点后两位。 接下来一行是一个整数 $N_2$（$N \le N_2 \le 1.5 \times N$），表示第二张地图上的总星星数。接下来的 $N_2$ 行以相同格式提供了第二张地图上星星的坐标。

输出应包含两行内容。第一行是一个整数 $K$，表示实际的死星数量。之后的 $K$ 行中，每行包含两个整数 $a_i$ 和 $b_i$，表示第一张地图上的第 $a_i$ 个星星和第二张地图上的第 $b_i$ 个星星为同一颗死星。注意，星星的编号从 1 开始。

测试数据的生成方式如下： - 预先确定死星的数量 $N$。 - 第一张和第二张地图上的星星数量 $N_1$ 和 $N_2$ 在 $1.0 \times N$ 和 $1.5 \times N$ 之间均匀随机选取。 - 随机生成 $N$ 个死星，坐标范围在 $-10000$ 到 $10000$ 之间。 - 为第一张地图和第二张地图分别生成 $N_1 - N$ 和 $N_2 - N$ 个额外星星，生成方式与死星相同。 - 为第一张地图生成一个平移向量 $(dx, dy)$，其中 $dx$ 和 $dy$ 在 $-10000$ 到 $10000$ 之间随机选取，所有星星偏移该向量。 - 生成一个旋转角度 $\theta$，在 $0$ 到 $2\pi$ 之间随机选取，将第一张地图上的每个点绕原点旋转 $\theta$。 - 第二张地图以同样方法生成并施加平移和旋转。 - 两张地图内的点顺序均被随机打乱。 - 测试案例保存时，每个点的坐标保留两位小数。 **本翻译由 AI 自动生成**