首页 / 软件开发 / 数据结构与算法 / 平面上有n个点 如何寻找距离最远的两个点

平面上有n个点 如何寻找距离最远的两个点2015-02-11一、问题描述

平面上有n个点，如何寻找距离最远的两个点？

二、解题思路

第一步，寻找凸包（因为最远距离的两个点一定在凸包上）

第二步，用旋转卡（qia）壳 寻找距离最大的点

凸包和旋转卡壳算法参见http://blog.csdn.net/kaytowin/article/details/5140111

三、代码实现

#include<iostream>#include<vector>#include<algorithm>#include<cmath>#include<stack>#define INF 100000000using namespace std;struct point{int x;int y;point（int x1,int y1）:x（x1）,y（y1）{}point（）{}};struct maxLS{point p1;point p2;int dist;maxLS（point pp1,point pp2,int dist1）:p1（pp1）,p2（pp2）,dist（dist1）{}maxLS（）{}};int xmult（point p1,point p2,point p0）{return （p1.x-p0.x）*（p2.y-p0.y）-（p2.x-p0.x）*（p1.y-p0.y）;}point p0（INF,INF）;vector<point> points;vector<point> pstack;void sort（vector<point>& points1）{for（int j=points.size（）-1;j>=1;j--）{for（int i=1;i<j;i++）{int xm=xmult（points[i],points[i+1],p0）;if（xm<0）{point tmp=points[i];points[i]=points[i+1];points[i+1]=tmp;}}}}//void printPoints（vector<point> ps）{for（int i=0;i<ps.size（）;i++）{cout<<"<"<<ps[i].x<<","<<ps[i].y<<">"<<endl;}}void convexHull（）{cout<<"打印输入点集:"<<endl;printPoints（points）;sort（points）;cout<<"打印按极角排序的点集:"<<endl;printPoints（points）;pstack.push_back（points[0]）;pstack.push_back（points[1]）;int stack_top=pstack.size（）-1;for（int i=2;i<points.size（）;i++）{stack_top=pstack.size（）-1;point pt2=pstack[stack_top];point pt1=pstack[stack_top-1];point ptcur=points[i];int xm=（pt2.x-pt1.x）*（ptcur.y-pt2.y）-（ptcur.x-pt2.x）*（pt2.y-pt1.y）;while（xm<0）{pstack.pop_back（）;stack_top=pstack.size（）-1;pt2=pstack[stack_top];pt1=pstack[stack_top-1];xm=（pt2.x-pt1.x）*（ptcur.y-pt2.y）-（ptcur.x-pt2.x）*（pt2.y-pt1.y）;}pstack.push_back（points[i]）;}cout<<"打印凸包点集:"<<endl;printPoints（pstack）;}int dist（point p1,point p2）{return （p2.x-p1.x）*（p2.x-p1.x）+（p2.y-p1.y）*（p2.y-p1.y）;}maxLS rotatingCalipers（）{int q=1;int maxLength=0;maxLS mls;for（int i=0;i<pstack.size（）-1;i++）{while（xmult（pstack[i+1],pstack[（q+1）%pstack.size（）],pstack[i]）>xmult（pstack[i+1],pstack[q],pstack[i]））{q=（q+1）%pstack.size（）;}int d1=dist（pstack[i],pstack[q]）;int d2=dist（pstack[i+1],pstack[q]）;if（d1>d2）{maxLength=d1;mls=maxLS（pstack[i],pstack[q],d1）;}else{maxLength=d2;mls=maxLS（pstack[i+1],pstack[q],d2）;}}return mls;}int main（）{cout<<"请输入节点数："<<endl;int n;cin>>n;cout<<"请输入"<<n<<"个节点:"<<endl;int p0i=0;int t=0;while（n--）{int x;int y;cin>>x>>y;if（y<p0.y||（y==p0.y&&x<p0.x））{p0.x=x;p0.y=y;p0i=t;}t++;points.push_back（point（x,y））;}point tmp=points[0];points[0]=points[p0i];points[p0i]=tmp;convexHull（）;maxLS maxL= rotatingCalipers（）;cout<<"两点最大距离："<<maxL.dist<<endl;cout<<"两点分别是:"<<"<"<<maxL.p1.x<<","<<maxL.p1.y<<">，";cout<<"<"<<maxL.p2.x<<","<<maxL.p2.y<<">"<<endl;system（"pause"）;return 0;}

四、输入：

9

3 1
4 3
5 2
3 5
6 5
8 4
5 7
2 6
1 4

五、输出：