我正在学习测试,我无法解决这个问题:
我们给出一组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