分治法：给定平面上n个白点和n个黑点，试s合计一个分治算法江每个白点和黑点向量，所有连线互不相交_给定平面上n个点,求红黑点匹配连线,连段不相交

自己分析：采用分治方法，寻找合适的中间界限，将大区间问题分成左右两个子区间，不通过递归过程求解。当然在其中的选择方式有很多，我们只要找到其中一种就可以。具体思路就是把大问题分解成两个子问题，然后从子问题中递归计算。这道题也可以采用贪心算法求解，这里主要考虑分治算法。

算法分析：

我们设P1..Pn为白点，Pn+1..P2n为黑点。我们采取分治采取分治策略寻找序列[Pp..Pr]中的配对方案(初始时[Pp..Pr]为[P1..P2n])，在[Pp..Pr]中找出一个最低位置(Y坐标值最小)的一个点P0,如果这样的点有多个,则选取最左边的点（即X坐标值的最小）为P0，P0与Pp交换。然后将其余点[Pp+1..Pr]按相对 Pp的极角递增的顺序排列，这里可以考虑凸包的求解方法，显然Pp与其余点Pp+1..Pr之间的任何线段是不会交叉的。我们从Pp开始寻找一个白点和黑点成对的最小子区间[Pp..Pi](p≤i≤r)。若该子区间仅剩一个元素,配对结束;否则白点黑点Pp与黑点白点Pi配对。这样使得尚未配对的白点黑点分布在两个子区间[Pp+1..Pi-1],[Pi+1..Pr]。继续按上述分治策略分别递归求解[Pp+1..Pi-1]和[Pi+1..Pr]。

图1：白色代表白点，黑色代表狠点

具体步骤：

1）如果黑白点集合为空，则停止，如果不为空，则执行2）。

2）寻找初试点P1，初始点为最左坐标标点，即X,Y坐标轴值都最小。

3）求解其他点相对于P1的极角。

4）对极角采用快速排序方法递增排序。

5）然后从P2开始顺序地找一个最短的配对序列P1－P6(黑白点的个数要相等，这样才能一一配对。P1－P6是3个白点，3个黑点)。

p1-p6求解是给黑点和白点一个标志，设黑点为-1，白点为1，从P1开始找时，逐渐累加，直到为0时停止，表明黑点和白点的个数相等，如P1到P2时：2个黑点(－1－1＝-2)，继续到P3：2个黑点一个白点(－1－1+1＝-1)，P4：三个黑点一个白点(-1-1+1-1＝-2)，P5：三个黑点一个白点(－1－1+1－1+1＝-1)，P6：3个黑点三个白点(－1－1+1－1+1+1＝0)，此时个数相等。

对成功分成的两部分p2-p5和p7-p8，采用上述方法递归计算。