我正在为考试而学习，但我无法解决这个问题：
我们得到一组n < 1000 个点和一个整数d。任务是创建两组不相交的点A_1和A_2（给定n个点的集合），使得每对点与A_i（对于 i = 1 或 2）之间的距离（欧几里得）小于或等于d。如果不可能，请打印-1。
例如，输入：
d = 3，并且点：
(5,3), (1,1), (4,2), (1,3), (5,2), (2,3), (5,1)
我们可以创建：
A_1 = { (2,3), (1,3), (1,1) }
A_2 = { (5,3), (4,2), (5,2), (5,1) }
因为来自 A_i 的每一对点（对于 i = 1 或 2）都足够接近。
我真的很想知道如何解决它，但不知道。由于n很小，算法甚至可以是O(n^2 log n)，但我不知道如何开始。我在想可能从计算每对点之间的距离开始，然后取两个最大距离的点并将它们放入不同的集合中（如果它们的距离大于 d）。然后对其余的对重复此步骤，但问题是如何决定我可以合法地将下一个点放在哪里。任何人都可以帮助这个算法吗？
让我们考虑一个具有n 个节点（对应于n个点）的简单图。如果两个对应点之间的距离大于d ，则连接两个节点。
如果可以创建两个不相交的集合，我们必须有一个二分图（如果一些节点不连接到其他节点，它们可以放在任何集合中）。
因此，我们只需要测试图的二分性，这很简单：
http://en.wikipedia.org/wiki/Bipartite_graph#Testing_bipartiteness
从距离矩阵开始似乎是个好主意。然后在这个距离矩阵中选择每个大于 d 的条目。此条目意味着相应的点必须位于不同的集合中。
从两个空集开始并迭代所有相关条目（> d）。
如果集合为空，则将两个点放入其中。否则有三种选择：
我刚刚想到了第二种方法，这种方法类似，但应该更快一些。
我们也从距离矩阵开始。
除了这两组之外，我们还维护一个堆栈、队列或任何新添加的条目。
因此，如果我们从距离矩阵中选择第一个相关条目，则这些点将添加到两个队列中。只要其中一个队列中有条目，请执行以下操作：
从队列中删除该点并将其插入到集合中。如果插入违反了最大距离标准，则问题无法解决。检查该点的距离矩阵中的行或列，并提取该行/列中的每个相关条目。将伙伴点添加到另一组的队列中（因为这必须在不同的组中）。
如果两个队列都是空的，则将下一个尚未访问的相关条目添加到队列中并重新开始。
该算法的优点是这些点按照它们可以相互影响的顺序进行处理。因此，不需要多于一对的集合。
想象一个数组，所有点都在顶部，所有点都在侧面。
如果定义单元格的两个点（左侧和顶部）相距大于 d，则在任何单元格中用零填充数组，如果两个点相距小于 d，则填充一个零。
(5,3), (1,1), (4,2), (1,3), (5,2), (2,3), (5,1)
(5,3), 0 1 0 1 1 1
(1,1), 0 0 1 0 1 0
(4,2), 1 0 0 1 1 1
(1,3), 0 1 0 0 1 0
(5,2), 1 0 1 0 0 1
(2,3), 1 1 1 1 0 0
(5,1) 1 0 1 0 1 0
（注意：您必须用翻转的相同 0 和 1 填充每个三角形。）
忽略对角线。注意右上角的三角形部分。
跳过第 0 列。
从第一列开始，如果顶行没有 1，则将其与右侧的另一列交换，该列在顶行有 1。然后也交换相同的行以保持对角线空白。（如果没有，则没有解决方案。） [示例：交换第 2 列和第 3 列以及第 2 和第 3 行] 请注意，该行的选择可能会成为优化因素。
移动到下一列，如果顶行没有 1，则与右侧的列交换并交换相应的行。如果没有，请尝试将其与下面的行交换，该行在该列中有 1 并执行相应的列。如果低于对角线，则应忽略其下方的行。
我们在三角形的左上角收集点，其中包含 1。这些点都可以放在其中一个集合中。
这就是我在脑海中迷失的地方，但是您必须从三角形的右下角开始执行类似的过程，并收集将在另一个集合中的点。交换行和对应的列以在三角形的右下角收集 1。
一旦你交换了足够多的行，你就可以在右上角形成一个矩形——一个没有左下角切掉的真正矩形——并且那个矩形包含所有的 0，你就有了一个解决方案。如果你不能这样做，就没有解决办法。
将三角形中的最低行与 1 进行比较，将三角形中最右侧的列与 1 进行比较，以及它们相遇的单元格。该单元格必须在三角形中才能存在解决方案。
（我给你留下了一个很大的“待办事项”来找到如何交错行和列的交换以清除三角形左上角和右下角的 0。也许这里的讨论可以解决如何制作它工作。或者发现它不起作用。）