CF958E3 Guard Duty (hard)

现在 Heidi 已经知道她可以将反叛者的飞船分配到基地（回忆简单子任务），她现在问你：具体应该怎么做？现在，给定平面上 $N$ 个飞船和 $N$ 个基地的位置，你的任务是将飞船和基地用线段连接，使得： - 这些线段互不相交。 - 这样的连接构成一个完美匹配。

第一行包含一个整数 $N$（$1 \leq N \leq 10000$）。对于 $1 \leq i \leq N$，第 $i+1$ 行包含两个整数 $x_{i}$ 和 $y_{i}$（$|x_{i}|, |y_{i}| \leq 10000$），表示第 $i$ 个飞船的坐标。接下来的 $N$ 行格式相同，表示基地的位置。保证没有两个点重合，且没有三点共线。

输出应有 $N$ 行。第 $i$ 行应包含一个整数 $p_{i}$，表示第 $i$ 个飞船连接到的基地的编号。序列 $p_{1},...,p_{N}$ 应构成 $1,...,N$ 的一个排列。 保证一定存在解。如果有多种方案，你可以输出其中任意一种。

由 ChatGPT 4.1 翻译