递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设δ=min{|p1-p2|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。
如图1所示。
我们注意到，如果S的最接近点对是{p3,q3}，即|p3-q3|<δ，则p3和q3两者与m的距离不超过δ，即|p3-m|<δ，|q3-m|<δ，也就是说，p3∈（m-δ,m]，q3∈（m,m+δ]。
由于在S1中，每个长度为δ的半闭区间至多包含一个点（否则必有两点距离小于δ），并且m是S1和S2的分割点，因此（m-δ,m]中至多包含S中的一个点。
同理，（m,m+δ]中也至多包含S中的一个点。
由图1可以看出，如果（m-δ,m]中有S中的点，则此点就是S1中最大点。
同理，如果（m,m+δ]中有S中的点，则此点就是S2中最小点。
因此，我们用线性时间就能找到区间（m-δ,m]和（m,m+δ]中所有点，即p3和q3。
从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。
选取分割点的选取通过分治法中“平衡子问题”的方法加以解决。
即：
m=[max（S）+min（S）]/2。
这个算法看上去比用排序加扫描的算法复杂，然而这个算法可以向二维推广。
二维的情形：
此时S中的点为平面上的点，它们都有2个坐标值x和y。
为了将平面上点集S线性分割为大小大致相等的2个子集S1和S2，我们选取一垂直线l（方程：
x=m）来作为分割直线。
其中m为S中各点x坐标的中位数。
由此将S分割为S1={p∈S|px≤m}和S2={p∈S|px>m}。
从而使S1和S2分别位于直线l的左侧和右侧，且S=S1∪S2。
由于m是S中各点x坐标值的中位数，因此S1和S2中的点数大致相等。
递归地在S1和S2上解最接近点对问题，我们分别得到S1和S2中的最小距离δ1和δ2。
现设δ=min（δ1,δ2）。
若S的最接近点对（p,q）之间的距离d（p,q）<δ则p和q必分属于S1和S2。
不妨设p∈S1，q∈S2。
那么p和q距直线l的距离均小于δ。
因此，我们若用P1和P2分别表示直线l的左边和右边的宽为δ的2个垂直长条，则p∈S1，q∈S2，如图2所示。
图2距直线l的距离小于δ的所有点
在一维的情形，距分割点距离为δ的2个区间（m-δ,m]（m,m+δ]中最多各有S中一个点。
因而这2点成为唯一的末检查过的最接近点对候选者。
二维的情形则要复杂些，此时，P1中所有点与P2中所有点构成的点对均为最接近点对的候选者。
在最坏情况下有n2/4对这样的候选者。
但是P1和P2中的点具有以下的稀疏性质，它使我们不必检查所有这n2/4对候选者。
考虑P1中任意一点p,它若与P2中的点q构成最接近点对的候选者，则必有d（p,q）<δ。
满足这个条件的P2中的点有多少个呢？
容易看出这样的点一定落在一个δ×2δ的矩形R中，如图3所示。
图3包含点q的δ×2δ的矩形R
由δ的意义可知P2中任何2个S中的点的距离都不小于δ。
由此可以推出矩形R中最多只有6个S中的点。
事实上，我们可以将矩形R的长为2δ的边3等分，将它的长为δ的边2等分，由此导出6个（δ/2）×（2δ/3）的矩形。
如图4（a）所示。
图4矩形R中点的稀疏性
若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个δ×2δ的小矩形中有2个以上S中的点。
设u,v是这样2个点，它们位于同一小矩形中，则
因此d（u,v）≤5δ/6<δ。
这与δ的意义相矛盾。
也就是说矩形R中最多只有6个S中的点。
图4（b）是矩形R中含有S中的6个点的极端情形。
由于这种稀疏性质，对于P1中任一点p，P2中最多只有6个点与它构成最接近点对的候选者。
因此，在分治法的合并步骤中，我们最多只需要检查6×n/2=3n对候选者，而不是n2/4对候选者。
我们只知道对于P1中每个S1中的点p最多只需要检查P2中的6个点，但是我们并不确切地知道要检查哪6个点。
为了解决这个问题，我们可以将p和P2中所有S2的点投影到垂直线l上。
由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于δ。
由上面的分析可知，这种投影点最多只有6个。
因此，若将P1和P2中所有S的点按其y坐标排好序，则对P1中所有点p，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者，对P1中每一点最多只要检查P2中排好序的相继6个点。
（二）程序代码
学生成绩系统的原代码
#include
#include
#include
#include
usingnamespacestd;
#defineT2//T代表两个学期
#defineC4//C代表四个班级
#defineP30//P代表每个班级最多为30人
#defineS5//S代表学生的5门课程
intN=0;//定义N为一个全局变量，用来储存实际从键盘输入的班级人数
classStu{//定义一个Stu类
private:
stringterm[T],clas[T][C],name[T][C][P];
intscore[T][C][P][S],total[T][C][P],average[T][C][P],people[T][C];
public:
voidsetsco（）;//用来完成按学期，按班级对学生成绩的录入
voidmendsco（）;//用来完成按学期，按班级对学生成绩的修改
voidadd（intn,intm）;//用来完成对某个班级进行增加学生的成绩
voidreduce（intn,intm）;//用来完成对某个班级进行减少学生
voidmend（intn,intm）;//用来完成对学生成绩的修改
voidtongji（）;//用来完成统计学生的总分和平均分，并按平均分对学生进行排序
voidfind（）;//用来完成对学生成绩的查找，以及不及格科目和学生名单
voidprint（）;//用来完成按班级输入成绩
voidsave（）;//用来保存学生的成绩
};
voidStu:
:
setsco（）{
inti,j,k,l=0;
for（i=0;icout<<"请输入学期:
";cin>>term[i];//输入学期
for（j=0;jcout<<"请输入班级:
";cin>>clas[i][j];//输入班级
cout<<"请输入这个班级的人数:
";cin>>N;
people[i][j]=N;
cout<<"请输入这个班级"<"<for（k=0;kcout<<"姓名:
";cin>>name[i][j][k];//输入学生的姓名
cout<<"汇编语言:
";cin>>score[i][j][k][l++];//输入学生的分数
cout<<"离散数学:
";cin>>score[i][j][k][l++];
cout<<"数字逻辑:
";cin>>score[i][j][k][l++];
cout<<"Ｃ++语言:
";cin>>score[i][j][k][l++];
cout<<"大学英语:
";cin>>score[i][j][k][l++];
l=0;
}
}
}
}
voidStu:
:
mendsco（）{
inti,j,choice=1;
cout<"<cout<"<cout<<"请选择一个学期:
";cin>>i;
cout<"<cout<"<cout<"<cout<"<cout<<"请选择一个班级:
";cin>>j;
while（choice）{
cout<添加人数"<cout<减少人数"<cout<修改学生的成绩"<cout<回主菜单"<cout<<"请输入一个数据:
";cin>>choice;
switch（choice）{
case1:
add（i-1,j-1）;break;//调用add（intn,intm）函数
case2:
reduce（i-1,j-1）;break;//调用reduce（intn,intm）函数
case3:
mend（i-1,j-1）;break;//调用mend（intn,intm）函数
case0:
break;
default:
cout<<"错了,请重新输入一个数据（0-3）:
";break;
}
}
}
voidStu:
:
add（intn,intm）{
inti,l=0,number,temp;//number用来储存需要添加的人数
cout<<"请输入需要添加的人数:
";cin>>number;
temp=people[n][m];
people[n][m]=people[n][m]+number;//该班的人数加上number
cout<<"请输入这"<"<for（i=temp;icout<<"姓名:
";cin>>name[n][m][i];//输入学生的姓名
cout<<"汇编语言:
";cin>>score[n][m][i][l++];
cout<<"离散数学:
";cin>>score[n][m][i][l++];
cout<<"数字逻辑:
";cin>>score[n][m][i][l++];
cout<<"Ｃ++语言:
";cin>>score[n][m][i][l++];
cout<<"大学英语:
";cin>>score[n][m][i][l++];
l=0;
}
}
voidStu:
:
reduce（intn,intm）{
inti,j,k,number,l=0,flag1,flag2=0;//number为需要减少的人数
stringflag;//flag用来储存从键盘输入的学生的名字
cout<<"请输入需要减少的人数:
";cin>>number;
cout<<"请输入这"<"<for（i=0;iflag1=0;
flag2=people[n][m];
cout<<"请输入第"<";
cin>>flag;
for（j=0;jif（name[n][m][j]==flag）{
for（k=j;kname[n][m][k]=name[n][m][k+1];//把后面学生的名字递补到前面来
score[n][m][k][l]=score[n][m][k+1][l];l++;
score[n][m][k][l]=score[n][m][k+1][l];l++;
score[n][m][k][l]=score[n][m][k+1][l];l++;
score[n][m][k][l]=score[n][m][k+1][l];l++;
score[n][m][k][l]=score[n][m][k+1][l];l++;
l=0;
}
people[n][m]--;//执行完上面的内容后，该班的人数减一
}
elseflag1++;
}
if（flag1==flag2）{cout<<"这个学生不存在,请重新输入!
"<}
}
voidStu:
:
mend（intn,intm）{
inti,j=0,l;
stringflag;//用来储存学生的姓名
cout<<"请您输入需要修改学生成绩的姓名:
";
cin>>flag;//从键盘输入学生的姓名
for（i=0;il=0;
if（name[n][m][i]==flag）{
cout<<"该学生的成绩如下"<cout<<"汇编语言:
";cout<cout<<"离散数学:
";cout<cout<<"数字逻辑:
";cout<cout<<"Ｃ++语言:
";cout<cout<<"大学英语:
";cout<l=0;
cout<<"现在请输入该生现在的新成绩:
"<cout<<"汇编语言:
";cin>>score[n][m][i][l++];
cout<<"离散数学:
";cin>>score[n][m][i][l++];
cout<<"数字逻辑:
";cin>>score[n][m][i][l++];
cout<<"Ｃ++语言:
";cin>>score[n][m][i][l++];
cout<<"大学英语:
";cin>>score[n][m][i][l++];
}
elsej++;
}
if（j==people[n][m]）cout<<"该学生不存在，请下次再重新输入!
";
}
voidStu:
:
tongji（）{
inti,j,k,l,m,n,flag=0;
stringflag1;
cout<"<cout<"<cout<<"请选择一个学期:
";cin>>i;
cout<"<cout<"<cout<"<cout<"<cout<<"请选择一个班级:
";cin>>j;
i--;j--;
for（k=0;kfor（l=0;ltotal[i][j][k]+=score[i][j][k][l];
average[i][j][k]=total[i][j][k]/S;
}
cout<cout<<"姓名"<for（m=0;mfor（n=0;nif（average[i][j][n]>average[i][j][n+1]）{
swap（average[i][j][n],average[i][j][n+1]）;
swap（name[i][j][n],name[i][j][n+1]）;
for（l=0;lswap（score[i][j][n][l],score[i][j][n+1][l]）;
}
for（k=0;kcout<for（l=0;lcout<cout<}
}
voidStu:
:
find（）{
inti,j=0,l,m,n,flag1,flag2=0;
stringflag;
cout<"<cout<"<cout<<"请选择一个学期:
";cin>>n;
cout<"<cout<"<cout<"<cout<"<cout<<"请选择一个班级:
";cin>>m;
n--;m--;
cout<<"请您输入需要查找学生成绩的姓名:
";
cin>>flag;//从键盘输入需要查找学生的姓名
for（i=0;il=0;
if（name[n][m][i]==flag）{
cout<<"该学生的成绩如下"<cout<<"汇编语言:
";cout<cout<<"离散数学:
";cout<cout<<"数字逻辑:
";cout<cout<<"Ｃ++语言:
";cout<cout<<"大学英语:
";cout<}
elsej++;//如果找不到该学生，J就加一
}
l=0;
if（j==people[n][m]）cout<<"该学生不存在，请下次再重新输入!
"<cout<<"不及格的情况如下:
"<for（i=0;iflag1=0;
if（score[n][m][i][l]<60）{cout<<"汇编语言:
"<if（score[n][m][i][l]<60）{cout<<"离散数学:
"<if（score[n][m][i][l]<60）{cout<<"数字逻辑:
"<if（score[n][m][i][l]<60）{cout<<"Ｃ++语言:
"<if（score[n][m][i][l]<60）{cout<<"大学英语:
"<if（flag1）cout<<"以上为"<elseflag2++;
}
if（!
flag2）cout<<"该班没有不及格的人."<}
voidStu:
:
save（）{
inti,j,k,l,m;
ofstreamout（"成绩系统.txt"）;//学生的成绩将保存在成绩系统.txt中
for（i=0;iout<for（j=0;jout<out<<"姓名"<for（l=0;lm=0;out<for（k=0,m=10;k{out<out<}
}
out<}
cout<<"学生的成绩已经成功地保存了!
"<}
voidStu:
:
print（）{
inti,j,k,l;
cout<"<cout<"<
升级会员 