平面上 n 个点和一个圆, 圆外 (不包括边界) 为 I 类点, 圆内 (包括边界) 为 II 类点. 每次可以消掉一对点 x,y, 满足: - x 为 I 类点, y 为 II 类点 - x,y 间的欧几里德距离不超过定值 d - 不存在还未消去, 且与 x 的距离不超过 d 的 II 类点 z,w, 使连线 x-y 与 z-w 相交
求最多可以消去多少个点, 并按顺序输出一种方案. (n ≤ 1000, 1 ≤ 坐标 ≤ 10^4, 1 ≤ d,半径R ≤ 2*10^4) 我们求的是最大匹配, 并且要求匹配具备某种拓扑序.
匈牙利算法有一个特点: 仅当走边表中前 k 条边无法增广, 才会考虑走第 (k+1) 条边. 不妨给边表排个序, 比划一下, 发现极角序就能满足需求. 这样一来, 我们发现 ans = 最大匹配 * 2.
怎样求方案呢? 暴力一下......迭代 ans/2 遍, 看看哪个点的配偶是自己剩下的邻居中的第一个 (已经排过序).
有种知其然不知其所以然的感觉......