n个点之间连线无交点的算法有关问题~100分
n个点之间连线无交点的算法问题~100分求助小弟今天拿到一到算法题,问题是这样的:平面上给出2n个随机点，n个
n个点之间连线无交点的算法问题~100分求助
小弟今天拿到一到算法题,问题是这样的:
平面上给出2n个随机点，n个红色，n个蓝色。要求写一个算法找出所有连线，使得一个红点只与一个蓝点相连，一个蓝点也只与一个红点相连（即满射），且连线之间不能有交点。（如下图）
小弟才疏学浅，请问各位大大，是否有与这题类似的算法可以参考？或者大家有什么好点子可以提点一下小弟的？
我现在的想法是利用有序表，找出相距最小的两个点（一红一蓝），然后连线。但是要怎么样用最有效的办法算出两条连线是否相交？
[解决办法]
没有三点共线的话，取线段总长最小的解就可以了。正确性证明见1979 Putnam A-4题。
用这个思路，做一个最大权匹配，就能在多项式时间里算出来了。用km算法或者费用流都可以。km可以做到n^3。
[解决办法]
>“取线段总长的最小解”指的是？
不管有没有相交，用n条线把这2n个红蓝点连起来，都算作一个方案。每一个方案都有一个n条线段的总长。这个总长如果是所有方案里最小的话，它就会不相交。
[解决办法]
求出所有红点到所有蓝点之间的距离，把这些距离列成一个n*n的矩阵，然后就转为了指派问题或二分图匹配问题，可以用km求解。不过本题的真正难点是正确性的证明，如果不是赶上FM大牛，一般还真不知道可以转为指派问题。
[解决办法]帮忙顶起&持续关注...
FM兄一楼的我没看懂。
看了3#和4#litaoye的回复，明白一些了。
功底不够啊，还得努力。
[解决办法]我觉得如果只是求解最短线段和，可能会造成很多情况的漏掉。因为楼主的题目要求是求解所有满足条件的解，而不是唯一的解。如果只是求解总和最短，那不是要漏掉些中间量吗？
如图，我觉得考虑最简单的递归算法，比如有n对红点和蓝点，挑出第一组边界上的红点和蓝点，只要满足其余的n-1对红点与蓝点的连线都位于这一组的同侧即可？当然不满足条件的就直接删去，最后剩下的就是所有满足条件的方案了。
[解决办法]可以增加一维时间坐标轴，设红点和蓝点的空间坐标分别是(xi,yi,zi,0)，(xxi,yyi,zzi,1)，规定只能t=0->1。
当n=2时，
对于不共线的四点连线A B只要满足A在B同侧或者B在A同侧即可。
对于共线的四点连线A B只要满足A∩B==NULL即可。当然因为限定了是红点和蓝点的连线，所以共线时有可能会无解。
[解决办法]不知道是否能用点求凸包的方法，就是把所有点的凸包求出来，在凸包多边形的边上，两个顶点是一红一篮的，就取出，余下的继续求凸包。如果遇到全部都是同色了，则对凸包内剩余的点再求凸包，之后再考虑怎么处理。
[解决办法]可不可以这样 楼主
任意取两点 （红点和黑点）假设他们连线的左边有偶数个点2m
右边 的点数就是 2n-2-2m也是偶数个 并且是不想交的
那么的 问题递归的 可以归结为 将左边的2m个点 再次进行划分
