P15827 [JOI Open 2014] 移民计划 / Project of Migration

这是一个**提交答案**题。 21XX 年，JOI 王国面临着一场巨大的危机。JOI 国王主动发起了一项移民计划，将人民迁移到新发现的 IOI 星球。 在 JOI 王国中，有 $N$ 个民族，编号从 1 到 $N$。其中有 $M$ 对民族之间存在着友好关系。在 IOI 星球上，有 $L$ 个居住区，编号从 1 到 $L$（$L \geq N$）。居住区 $i$ 是坐标平面上的点 $P_i(X_i, Y_i)$（$1 \leq i \leq L$）。在移民计划中，我们需要为每个民族分配一个居住区。同一个居住区不能被分配给多个民族。 对于每一对存在友好关系的民族，我们将修建一条连接它们所在居住区的铁路轨道。铁路轨道是连接两个居住区的线段。根据居住区的分配方式，可能会出现两条铁路轨道相交的情况。 应国王的要求，你需要找到一个使得相交的铁路轨道对数最少的移民方案。 ### 任务 给定 JOI 王国的民族信息以及 IOI 星球上居住区的信息，找出一个使得相交的铁路轨道对数最少的移民方案。

共有五个子任务。每个子任务对应一个公开的输入数据文件。每个输入数据文件的格式如下。 - 输入的第一行包含两个以空格分隔的整数 $N$ 和 $M$。这表示 JOI 王国有 $N$ 个民族，并且有 $M$ 对存在友好关系的民族。 - 接下来的 $M$ 行中，第 $j$ 行（$1 \leq j \leq M$）包含两个以空格分隔的整数 $A_j$ 和 $B_j$。这表示民族 $A_j$ 和民族 $B_j$ 存在友好关系。 - 接下来的一行包含一个整数 $L$，表示 IOI 星球上居住区的数量。 - 接下来的 $L$ 行中，第 $i$ 行（$1 \leq i \leq L$）包含两个以空格分隔的整数 $X_i$ 和 $Y_i$。这表示居住区 $i$ 是坐标平面上的点 $P_i(X_i, Y_i)$。 ### 注意 根据居住区的分配方式，可能会出现两条以上的铁路轨道交于一点的情况。

对于每个输入数据文件，你需要提交一个对应的输出数据文件。输出数据文件应由 $N$ 行组成。第 $k$ 行（$1 \leq k \leq N$）应包含一个整数，表示分配给民族 $k$ 的居住区编号。

### 样例 1 解释 在此样例输入中，IOI 星球上有七个居住区，如下图所示。 :::align{center}  ::: 有六个民族。我们为每个民族分配一个居住区，分配方案如下： - 将居住区 1 分配给民族 1。 - 将居住区 5 分配给民族 2。 - 将居住区 4 分配给民族 3。 - 将居住区 2 分配给民族 4。 - 将居住区 7 分配给民族 5。 - 将居住区 3 分配给民族 6。 我们将修建如下图所示的多条铁路轨道。相交的铁路轨道对数为 2。 ### 约束条件 所有输入数据满足以下条件。 - $1 \leq A_j \leq N$。 - $1 \leq B_j \leq N$。 - $1 \leq X_i \leq 100\,000$。 - $1 \leq Y_i \leq 100\,000$。 - $P_i, P_j, P_k$ 不共线（$1 \leq i < j < k \leq L$）。 - 对于任意两个民族，我们总可以沿着 IOI 星球上的若干条铁路轨道，从一个民族的居住区旅行到另一个民族的居住区。 :::align{center}  ::: - 连接居住区 1（民族 1 所在地）和居住区 4（民族 3 所在地）的铁路轨道，与连接居住区 2（民族 4 所在地）和居住区 3（民族 6 所在地）的铁路轨道相交。 - 连接居住区 1（民族 1 所在地）和居住区 4（民族 3 所在地）的铁路轨道，与连接居住区 2（民族 4 所在地）和居住区 5（民族 2 所在地）的铁路轨道相交。 ### 子任务 对于每个子任务，$N$、$M$、$L$、$S$、$T$ 的值如下表所示。关于 $S$ 和 $T$ 的具体含义，请参见评分细则。 | 子任务 | $N$ | $M$ | $L$ | $S$ | $T$ | | :----: | :---: | :-----: | :---: | :------: | :-------: | | 1 | 30 | 50 | 60 | 25 | 100 | | 2 | 125 | 124 | 300 | 0 | 75 | | 3 | 200 | 2000 | 400 | 110000 | 250000 | | 4 | 250 | 350 | 250 | 400 | 2000 | | 5 | 300 | 1600 | 500 | 72000 | 150000 | ### 评分细则 这是一个**提交答案**任务。共有五个子任务，每个子任务包含一个输入数据文件。你需要为每个子任务提交一个对应的输出数据文件。每个子任务的得分计算方式如下： - 如果你的移民方案不满足题目描述中的条件，则得分为 0。 - 如果你的移民方案满足题目描述中的条件，则根据 $S$ 和 $T$ 的值按下述方式计算得分。设 $C$ 为相交的铁路轨道对数。 - 如果 $T < C$，得分为 0。 - 如果 $S < C \leq T$，得分为 $\left\lfloor 1 + 19 \times \left( \frac{T - C}{T - S} \right)^2 \right\rfloor$。其中 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。 - 如果 $C \leq S$，得分为 20。 翻译由 DeepSeek V3.2 完成