分治求点集中的最近距离 version 0.1

本文主要是介绍分治求点集中的最近距离 version 0.1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//
//  main.cpp
//  MinPointDistance
//
//  Created by 孙江涛 on 13-9-29.
//  Copyright (c) 2013年 bryan. All rights reserved.
//#include <iostream>
#include <vector>
#include <math.h>using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::sort;struct Point
{double x;double y;
};struct Result
{Point p1;Point p2;double distance;
};bool sortTwoPointByX(const Point &p1,const Point &p2)
{return p1.x < p2.x;
}bool sortTwoPointByY(const Point &p1,const Point &p2)
{return p1.y < p2.y;
}void sortPointVecByX(vector<Point> &pointVec)
{sort(pointVec.begin(),pointVec.end(),sortTwoPointByX);
}void sortPointVecByY(vector<Point> &pointVec)
{sort(pointVec.begin(),pointVec.end(),sortTwoPointByY);
}void divideVector(vector<Point> &pointVec,vector<Point> &pointVec0,vector<Point> &pointVec1)
{size_t size = pointVec.size();for(vector<Point>::iterator it = pointVec.begin();it < pointVec.begin()+size/2;++it ){Point p;p.x = (*it).x;p.y = (*it).y;pointVec0.push_back(p);}for(vector<Point>::iterator it = pointVec.begin()+size/2;it < pointVec.end();++it ){Point p;p.x = (*it).x;p.y = (*it).y;pointVec1.push_back(p);}}double PointDistance(Point p1,Point p2)
{return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double MinPointDistance(double d1,double d2)
{if(d1>=0&&d2>=0){if(d1 - d2 <= 0)return d1;if(d1 - d2 >0)return d2;}if(d1>=0&&d2<0){return d1;}if(d1<0&&d2>=0){return d2;}return 0;
}double MinDistanceInSet(vector<Point> &pointVec)
{size_t size= pointVec.size();if(2 == size){return PointDistance(pointVec[0],pointVec[1]);}else if(3 == size){return MinPointDistance(PointDistance(pointVec[0], pointVec[1]), MinPointDistance(PointDistance(pointVec[1], pointVec[2]), PointDistance(pointVec[0], pointVec[2])));}else if(size>=4){sortPointVecByX(pointVec);vector<Point> pointVec0;vector<Point> pointVec1;divideVector(pointVec, pointVec0, pointVec1);double minDistanceInTwoPart = MinPointDistance(MinDistanceInSet(pointVec0),MinDistanceInSet(pointVec1));Point middlePoint = pointVec[size/2];vector<Point> pointVec2;for (vector<Point>::iterator it = pointVec.begin(); it<pointVec.end(); ++it){Point p;p.x = (*it).x;p.y = (*it).y;if(fabs(p.x-middlePoint.x) < minDistanceInTwoPart && p.x!= middlePoint.x){pointVec2.push_back(p);}}sortPointVecByY(pointVec2);double minDistance = MinPointDistance(MinDistanceInSet(pointVec2), minDistanceInTwoPart);return minDistance;}return -1;
}int main(int argc, const char * argv[])
{vector <Point> pointVec;vector <Point> pointVec0;vector <Point> pointVec1;Point p;while(cin>>p.x>>p.y){pointVec.push_back(p);}cout<<MinDistanceInSet(pointVec)<<endl;return 0;
}

这篇关于分治求点集中的最近距离 version 0.1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---