[ABC373G] No Cross Matching 题解

· · 题解

题意

给定二维平面上 n 个红点和 n 个黑点，将他们两两匹配形成若干条线段，使得任意两条线段不交，求方案。

分析

看到很多大佬用网络流做，但是我不太会。

首先多画几个图就不难发现不会出现无解的情况（一会给出的构造方案也可说明）。

先将未匹配的所有点按 x，y 坐标双关键字排序。然后我们可以取 x 坐标最小的点（若有多个，则取 y 坐标最小的点）为特殊点，将其余所有未匹配的点与他连线，按线段斜率大小升序排序。由于不存在三点共线，因此每条线段的斜率均不同。

接着按顺序遍历这些点。当找到一个点使得这个点与特殊点的连线将未匹配的点分为上下两部分，且上下两部分中红黑点数量分别相同时，则连接这条线段，然后将上下两部分递归求解。容易证明这种构造方案一定符合条件。

时间复杂度 O(n^2\log n)。

code