一. 用分治算法解平面最接近点对问题1.题目关于最接近点对问题:给定平面上n个点，找出其中一对点，使得在n个点所构成的所有点对中，该点对的距离最小。
2.程序详细介绍(各模块的功能等)本程序主要包括两个类:类Point和类Ppoint.其中类Point为处理一些的基本数据传递等.类Ppoint为该程序的主要实现模块,该类中有输入点对的函数shuru,对所输入的点对按X轴排序的函数sort,求各点对的距离的函数xiao等.假设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.此即为该程序的大致算法.3. 程序结构（流程图）该程序的流程图如下所示4. 调试与测试：调试方法，测试结果（包括输入数据和输出结果）的分析与讨论运行该程序时,屏幕上会出现一个界面,首先该界面会提示输入要处理的点对个数,输入点对个数后从键盘输入数字0即可显示出处理后的各个结果,会出现如下结果:5.程序代码(源程序)#include<iostream>#include<cmath>#include<fstream>using namespace std;int i,j,k,d,m,n;double p2,q,s,r,t;class Point //创建一个点类//{public:double x;double y;double getx(){return x;}double gety(){return y;}friend class Ppoint;};class Ppoint{int sum;double juli[10][10];double min[11]; //min[10]用来存放每组中最短的距离//double mini[11]; //mini[10]用来存放每组中距离最短的点对中的第一个点//double minj[11]; //minj[10]用来存放每组中距离最短的点对中的第二个点//Point p[100];Point p1;public:void shuru(){cout<<"请输入要处理的点的个数"<<endl;cin>>sum;for(i=0;i<sum;i++){cout<<"请输入点对"<<endl;cin>>p[i].x;cin>>p[i].y;cout<<p[i].x<<","<<p[i].y<<endl;}}void sort(){cout<<"以下是按x轴上由小到大排序后的点对"<<endl;for(i=0;i<sum-1;i++){for(j=i+1;j<sum;j++){if(p[i].x>p[j].x){p1=p[i];p[i]=p[j];p[j]=p1;}}}for(i=0;i<sum;i++){cout<<p[i].x<<","<<p[i].y<<endl;}}void xiao(){cout<<"以下是对每个模块中的点求距离"<<endl;for(k=0;k<sum/10;k++){cout<<"按任意键继续"<<endl;cin>>i;cout<<"以下是第"<<k<<"个模块中的距离"<<endl;for(i=1;i<10;i++){for(j=0;j<i;j++){r=abs(p[k*10+i].x-p[k*10+j].x);t=abs(p[k*10+i].y-p[k*10+j].y);juli[i][j]=sqrt(r*r+t*t);cout<<juli[i][j]<<"\t";}cout<<endl;}min[k]=juli[k][0],mini[k]=10*k+1,minj[k]=10*k;for(i=1;i<10;i++){cout<<"\n"<<"第"<<i<<"行以前的最小值为"<<min[k]<<endl;for(j=0;j<i;j++){if(juli[i][j]<min[k]){min[k]=juli[i][j];mini[k]=10*k+i;minj[k]=10*k+j;}}}cout<<"\n"<<"这是第"<<k<<"个模块中的结果"<<endl;cout<<"\n"<<"距离最小值为"<<min[k]<<endl;cout<<"\n"<<"距离最小值的第一个点为"<<mini[k]<<endl; //cout<<"距离最小值的第一个点为"<<mini[k]<<endl;//}if(sum%10!=0){k=sum/10;cout<<"输入0显示结果"<<endl;cin>>i;for(i=1;i<sum%10;i++){for(j=0;j<i;j++){m=abs(p[k*10+i].x-p[k*10+j].x);n=abs(p[k*10+i].y-p[k*10+j].y);juli[i][j]=sqrt(m*m+n*n);cout<<juli[i][j];cout<<"\t";}cout<<endl;}min[k]=juli[1][0],mini[k]=10*k+1,minj[k]=10*k;for(i=1;i<sum%10;i++){cout<<"\n"<<"第"<<i<<"行以前的最小值为"<<min[k]<<endl;for(j=0;j<i;j++){if(juli[i][j]<min[k]){min[k]=juli[i][j];mini[k]=10*k+i;minj[k]=10*k+j;}}}cout<<"\n"<<"这是第"<<k<<"个模块中的结果"<<endl;cout<<"\n"<<"距离最小值为"<<min[k]<<endl;cout<<"\n"<<"距离最小值的第一个点为"<<mini[k]<<endl; //cout<<"距离最小值的第一个点为"<<mini[k]<<endl;}}void realmin(){cout<<"\n"<<"几个模块中的最小值是："<<min[10]<<endl;for(i=0,min[10]=min[0],mini[10]=mini[0],minj[10]=minj[0];i<=sum/10;i++){if(min[i]<min[10]){min[10]=min[i];mini[10]=mini[i];minj[10]=minj[i];}}}void bianjiemin(){cout<<"\n"<<" 包括边界的最小值是："<<min[10]<<endl;for(i=0;i<sum/10;i++){for(k=9;k>=0;k--)if(p[(i+1)*10].x-p[i*10+k].x<min[10]){for(q=0;q<10;q++)if(p[(i+1)*10+m].x-p[(i+1)*10].x<min[10]){m=abs(p[i*10+k].x-p[(i+1)*10+m].x);n=abs(p[i*10+k].y-p[(i+1)*10+m].y);if(min[10]>sqrt(m*m+n*n)){min[10]=sqrt(m*m+n*n);mini[10]=i*10+k;minj[10]=(i+1)*10+q;}}elsebreak;}elsebreak;}}void shuchu(){i=mini[10];j=minj[10];p2= abs(p[i].x-p[j].x)*abs(p[i].x-p[j].x) ;q= abs(p[i].x-p[j].x)*abs(p[i].x-p[j].x) ;s=sqrt(p2+q);cout<<"\n"<<"最接近点对为"<<"p["<<i<<"]"<<"("<<p[i].x<<","<<p[i].y<<")"<<" "<<"p["<<j<<"]"<<"("<<p[j].x<<","<<p[j].y<<")"<<endl;cout<<"\n"<<"最短距离为"<<min[10];cout<<"\n"<<"最短距离为"<<s;}};int main(){Ppoint x;x.shuru();x.sort();x.xiao();x.realmin();x.bianjiemin();x.shuchu();return 0;}二.设计体会通过这次的课程设计，我对C++程序语言有了更进一步的认识。