SP202 ROCKETS - Rockets

在一个二维地图上，有两个分别包含 $n$ 个点的独立点集：**R** 和 **W**。这两组点加起来，任意三个点都不共线。集合 **R** 中的点是地对地导弹的发射地点，而集合 **W** 中的点是需要摧毁的敌方目标。导弹只能沿直线飞行，而且它们的飞行路径不能彼此相交。我们的目标是为每个导弹找到一个对应的目标。 ### 任务目标 编写一个程序，要能： - 从标准输入中获取集合 **R** 和 **W** 中点的坐标， - 计算出 $n$ 条互不相交的线段，每条线段的一端来自集合 **R**，另一端来自集合 **W**， - 将结果写入标准输出。

第一行是一个整数 $t$，表示测试用例的数量，随后的输入由 $t$ 个测试用例组成，每个测试用例之间用空行隔开。每个测试用例的第一行包含一个整数 $n$，表示集合 **R** 和 **W** 中点的个数，$1 \le n \le 10000$。 接下来的 $2n$ 行中，每行包含两个用空格分隔的整数，表示地图上点的坐标（先 $x$ 坐标，后 $y$ 坐标），取值范围在 $[-10000, 10000]$。前 $n$ 行是集合 **R** 中点的坐标，接下来的 $n$ 行是集合 **W** 中点的坐标。第 $(i+1)$ 行是点 $r_i$ 的坐标，第 $(i+n+1)$ 行是点 $w_i$ 的坐标，$1 \le i \le n$。

对于每个测试用例，输出包含 $n$ 行。第 $i$ 行应当输出一个整数 $k(i)$，表示线段 $r_i w_{k(i)}$ 是程序找到的线段集中的一条。（这意味着，从点 $r_i$ 发射的导弹成功摧毁了位于点 $w_{k(i)}$ 的目标。） **本翻译由 AI 自动生成**