一、问题描述
平面上有n个点，如何寻找距离最远的两个点？
二、解题思路
第一步，寻找凸包（因为最远距离的两个点一定在凸包上）
第二步，用旋转卡(qia)壳 寻找距离最大的点
凸包和旋转卡壳算法参见http://blog.csdn.net/kaytowin/article/details/5140111
三、代码实现
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<stack>
#define INF 100000000
using 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;
}
}
}
}
//更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
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
五、输出：
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， 寻找源代码
， include
， 凸包问题
， vector
， 距离最远
， 凸包
， point
， 两个
， 三维凸包
， 寻找平面上的极大点
， n个点
寻找代码
海平面目测最远距离、寻找最远点对、excel 寻找最远的日期、wifi最远传输距离、7.1最远距离宏，以便于您获取更多的相关知识。