题目分析

本题是 JOI Open 2014 Day2 T1「移住計画 / Project of Migration」，属于计算几何与图论相结合的优化问题。题目要求将 $N$ 个民族分配至 $L$ 个给定的坐标点（$L \geq N$），每个民族占据一个不同的居住区，并在具有友好关系的民族对之间建立直线铁路轨道。目标是最小化铁路轨道之间的交叉对数。

---

问题建模

1. 基本符号

• 图 $G = (V, E)$，其中 $V = \{1, \dots, N\}$ 是民族集合，$E$ 是 $M$ 条友好关系边。
• 点集 $P = \{P_1, \dots, P_L\}$，其中 $P_i = (X_i, Y_i)$。
• 分配方案 $\pi: V \to \{1, \dots, L\}$，为单射。
• 对每条边 $e = (u, v) \in E$，对应线段 $[\pi(u), \pi(v)]$。

2. 交叉数定义

定义 交叉数 $C(\pi)$ 为： $ C(\pi) = \#\{ \{e_1, e_2\} \subseteq E : e_1 \neq e_2, \text{线段}[\pi(u_1),\pi(v_1)] \text{与} [\pi(u_2),\pi(v_2)] \text{在内部相交} \} $ 注意：

• 只统计内部相交（端点相交不计）。
• 允许多于两条边交于同一点（这种特殊情况不影响计数）。
• 目标是求 $\min_{\pi} C(\pi)$。

---

理论性质与难点

1. 完全图情况

若 $G$ 是完全图 $K_N$，则问题等价于：在 $L$ 个点中选 $N$ 个点，将 $K_N$ 直线段画在这些点上，最小化交叉数。
已知结论（交叉数理论）：完全图 $K_N$ 的直线段画在任意点集上的最小交叉数为 $\Theta(N^4)$，但当点集呈凸位置时，最小交叉数为 $\binom{N}{4}$（任意四条点确定的四边形产生一对交叉）。这提示我们：当 $G$ 稠密时，应优先选择凸包上的点分配给度数大的顶点。

2. 稀疏图情况

$M$ 较小时，可能找到无交叉的分配（即 $C=0$），这等价于将 $G$ 平面直线段嵌入到给定点集 $P$ 的某个子集上。
已知判定一个图能否直线段画在给定点集上无交叉是 NP-hard 问题（即使 $G$ 是匹配）。因此本题必须用启发式方法。

3. 交叉的几何判定

两线段 $AB$ 与 $CD$ 在内部相交的充分必要条件是： $ \text{ccw}(A,C,D) \neq \text{ccw}(B,C,D) \quad \text{且} \quad \text{ccw}(A,B,C) \neq \text{ccw}(A,B,D) $ 其中 $\text{ccw}(P,Q,R)$ 表示点 $P,Q,R$ 的逆时针方向（>0 逆时针，<0 顺时针，=0 共线）。利用此公式可在 $O(1)$ 判断一对边是否交叉。

---

启发式算法思路

1. 局部搜索（Local Search）

初始分配可以随机或贪心生成，然后反复尝试交换两个民族的居住区，若交换减少 $C$ 则接受。
计算 $C$ 的变化量 $\Delta C$ 可只考虑涉及交换顶点的边，这样单次更新复杂度 $O(\deg^2)$ 而非 $O(M^2)$。

2. 模拟退火（Simulated Annealing）

局部搜索易陷入局部最优，可用模拟退火：以概率 $e^{-\Delta C / T}$ 接受较差解。
温度 $T$ 从高到低衰减，迭代足够次数。
每次随机选取两个民族交换，计算 $\Delta C$。

3. 基于点集几何结构的贪心

观察数据范围 $X_i, Y_i \leq 10^5$，点集 $P$ 一般分布均匀，无三点共线。策略：

• 计算 $P$ 的凸包，将凸包上的点分配给 $G$ 中度数最大的顶点集合。
• 理由：凸包上的边较少与其他边交叉（仅在凸包内部穿出时才易交叉）。
• 内部点按某种空间填充曲线（如 Hilbert 曲线）排序，再按顶点 BFS 序分配，使相邻顶点在几何上接近，减少边长从而减少交叉。

4. 增量构造

按某种顺序（如度数从大到小）依次为顶点选择居住区，每次选择使当前已确定边交叉数增加最小的未使用点。
这需要维护已画出的边集合，对新点 $p$ 与已分配点的所有边判断交叉。复杂度 $O(N^3)$，$N \leq 300$ 时可行。

5. 利用图的平面性子图

若 $G$ 是平面图，理论上可画在任意点集上使得边为直线段且无交叉（Fáry 定理），但要求点集任意，而本题点集固定，故不一定能 $C=0$。但我们可以：

1. 找出 $G$ 的一个最大平面子图 $G'$。
2. 将 $G'$ 嵌入到 $P$ 的一个子集上，尽量无交叉。
3. 将剩余的边加上，此时必然产生交叉，但尽量少。

---

交叉数计算优化

直接计算 $C(\pi)$ 需 $O(M^2)$ 对边检查，$M$ 可达 $2000$，可行。但在模拟退火中需多次计算，需优化：

• 维护一个 $M \times M$ 的交叉矩阵（布尔型），更新时只修改涉及交换顶点的边对应的行和列。
• 用 bitset 加速交叉检测：将点编号，预计算每对点是否可能连线（无直接用处），但对 $M^2$ 检查，$M=2000$ 时 $4\times 10^6$ 次 ccw 计算可接受。

---

针对测试点特性的策略

观察 5 个测试点的参数：

测试点	$N$	$M$	$L$	特点
1	30	50	60	小规模，可较精确优化
2	125	124	300	$M=N-1$，$G$ 是树
3	200	2000	400	稠密图，近似完全图
4	250	350	250	$L=N$，点与顶点一一对应
5	300	1600	500	较大规模，中等密度

针对性方法：

1. 测试点 2：$G$ 是树（$M=N-1$）。树总可以画在平面上无交叉（平面图），但要画在固定点集上可能仍需交叉。可使用双重心法：选根，DFS 序映射到点集的某种顺序，尽量使父子在几何上接近。
2. 测试点 3：$M=2000$，$N=200$，接近完全图。重点利用凸包点分给大度数顶点。
3. 测试点 4：$L=N$，必须用尽所有点。此时问题是经典图绘制在固定点集，无选择余地。可尝试迭代改善：交换顶点对应的点，直接优化。
4. 测试点 1 和 5：可用模拟退火结合贪心初始解。

---

几何技巧

1. 极角排序

对每个已选点 $p$，将其他点按相对于 $p$ 的极角排序，快速判断射线穿过的边，用于估计交叉数。

2. 交叉数下界估计

对于 $G$，已知其交叉数（crossing number）$\text{cr}(G)$ 是画在平面上任意位置的最小交叉对数（边可弯曲）。直线段画在固定点集上的交叉数 $\geq \text{cr}(G)$。可计算一个松弛下界。

3. 分治策略

将点集用一条直线分成两半，将 $G$ 的顶点按某种割平衡分配至两侧，使连接两侧的边尽量少。递归进行。

---

实现流程建议

1. 读入数据，计算每个顶点度数 $\deg(v)$。
2. 点集处理：计算凸包，对凸包点按顺时针编号；内部点按 $x$ 坐标或 Hilbert 曲线顺序编号。
3. 初始分配：
   • 将凸包点按度数从大到小分配给顶点。
   • 剩余顶点按 BFS 序（从已分配的高度数顶点出发）分配剩余点，选择使当前交叉数增加最小的点。
4. 局部优化：
   • 重复多次：随机选两个顶点，计算交换后的 $\Delta C$，若 $\Delta C < 0$ 或按模拟退火概率接受，则交换。
   • 可并行尝试多个随机种子。
5. 输出最终分配。

---

理论启示

本题是固定点集上的直线段图绘制（Straight-line graph drawing on fixed vertex locations）的交叉数最小化问题。在计算几何中，即使判定 $C=0$ 是否可能也是 NP-hard。因此，JOI 官方对本题的评分机制（$S$ 和 $T$）允许非最优解：只要 $C \leq T$ 即可得分，$C \leq S$ 可得满分 $20$ 分。

这表明在实际比赛中，不必追求绝对最优，而应设计稳定的启发式算法，在时限内得到 $C$ 较小的解。

---

总结

本题结合了：

• 图论：顶点分配、交叉数概念。
• 计算几何：线段相交判定、凸包、点集排序。
• 组合优化：启发式搜索、局部改进。

核心思想是：利用点集的几何结构指导顶点分配，再通过局部交换迭代优化交叉数。