首页 > 代码库 > 编程之美-2.11 扩展 寻找距离最远的两个点
编程之美-2.11 扩展 寻找距离最远的两个点
一、问题描述
平面上有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; } } } } 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
五、输出:
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。