编程之美2.11
// Test.cpp : Defines the entry point for the console application.
//
#include <vector>
#include<time.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<limits.h>
#include<assert.h>
#include<float.h>
using namespace std;
time_t t1,t2;
void Tic()
{
t1=time(NULL);
// for(int i=0;i<INT_MAX;++i);
}
void Toc()
{
t2=time(NULL);
std::cout<<"time:"<<(t2-t1)/3600<<"时:"<<(t2-t1)%3600/60<<"分:"<<(t2-t1)%60<<"秒"<<std::endl;
}
int RandInt(int low,int high)
{
float temp=rand()/(static_cast<float>(RAND_MAX));
int k=low+static_cast<int>((high-low)*temp);
return k;
}
struct Point
{
float x;
float y;
int tag;//数据唯一性标志
Point():x(0),y(0)
{
}
Point(float xx,float yy):x(xx),y(yy)
{
}
Point &operator=(const Point& p)
{
this->x=p.x;
this->y=p.y;
this->tag=p.tag;
return *this;
}
friend bool operator==(const Point &p1,const Point &p2);
void Init(const float xx,const float yy);
friend ostream& operator<<(ostream &out,const Point &p);
};
bool operator==(const Point &p1,const Point &p2)
{
if(abs(p1.tag-p2.tag)<1e-8)return true;
else return false;
}
void Point::Init(const float xx,const float yy)
{
x=xx;
y=yy;
}
ostream& operator<<(ostream &out,const Point &p)
{
out<<"tag:"<<p.tag<<" ("<<p.x<<","<<p.y<<") ";
return out;
}
float Diff(const Point& p1,const Point &p2)
{
float dis=sqrt(pow(p1.x-p2.x,2)+pow(p1.y-p2.y,2));
return dis;
}
struct CompareX
{
bool operator()(const Point &p1,const Point &p2)const
{
if(p1.x<p2.x)return true;
else return false;
}
};
struct CompareY
{
bool operator()(const Point &p1,const Point &p2)const
{
if(p1.y<p2.y)return true;
else return false;
}
};
void Init(vector<Point>&pVX,vector<Point>&pVY,const int size)
{
//初始化产生点对
for(int i=0;i<size;++i)
{
float xx,yy;
xx=static_cast<float>(RandInt(0,size));
yy=static_cast<float>(RandInt(0,size));
Point tempPoint(xx,yy);
tempPoint.tag=i;
pVX.push_back(tempPoint);
pVY.push_back(tempPoint);
}
}
void PrintVector(const vector<Point>&pV)
{
int i=0;
for(std::vector<Point>::const_iterator ite=pV.begin();ite!=pV.end();++ite,++i)
{
if(i!=0&&i%10==0)std::cout<<std::endl;
std::cout<<*ite<<std::endl;
}
std::cout<<std::endl;
}
void FindMin1(const vector<Point>&pV,int low,int high,Point &first,Point &last,float &minDis)
{
minDis=FLT_MAX;
first.Init(FLT_MIN,FLT_MIN);
last.Init(FLT_MAX,FLT_MAX);
for(int i=low;i<high;++i)
{
for(int j=i+1;j<=high;++j)
if(Diff(pV[i],pV[j])<minDis)
{
minDis=Diff(pV[i],pV[j]);
first=pV[i];
last=pV[j];
}
}
}
vector<Point>temptV;
void FindMin22(const vector<Point>&pVX,const vector<Point>&pVY,int low,int high,Point &first,Point &last,float &minDis)
{ //算法导论求二维空间最小点对 标准方法
if(high-low<3)
{
minDis=FLT_MAX;
for(int i=low;i<high;i++)
{
for(int j=i+1;j<=high;j++)
if(Diff(pVX[i],pVX[j])<minDis)
{
minDis=Diff(pVX[i],pVX[j]);
first=pVX[i];
last=pVX[j];
}
}
}
else
{
int mid=(low+high)/2;
Point lFirst,lLast,rFirst,rLast;
float lMinDis,rMinDis;
lMinDis=FLT_MAX;
rMinDis=FLT_MAX;
vector<Point>lPVY,rPVY;
for(int i=0;i<pVY.size();i++)
{
if(pVY[i].x<pVX[mid].x)
lPVY.push_back(pVY[i]);
else if(pVY[i].x>pVX[mid].x)
rPVY.push_back(pVY[i]);
else
{
for(int k=mid;k>=low&&pVX[k].x==pVY[i].x;k--)
if(pVX[k].tag==pVY[i].tag){lPVY.push_back(pVY[i]);break;}
for(int k=mid+1;k<=high&&pVX[k].x==pVY[i].x;k++)
if(pVX[k].tag==pVY[i].tag){rPVY.push_back(pVY[i]);break;}
}
}
assert(lPVY.size()==mid-low+1);
assert(rPVY.size()==high-mid);
FindMin22(pVX,lPVY,low,mid,lFirst,lLast,lMinDis);
FindMin22(pVX,rPVY,mid+1,high,rFirst,rLast,rMinDis);
minDis=min(lMinDis,rMinDis);//
vector<Point>Y;
for(int i=0;i<pVY.size();i++)
if(abs(pVY[i].x-pVX[mid].x)<=minDis)Y.push_back(pVY[i]);
for(int i=0;i<Y.size();i++)
{
for(int j=i+1;j<=i+7&&j<Y.size();j++)
if(Diff(pVY[i],pVY[j])<minDis)
{
minDis=Diff(pVY[i],pVY[j]);
first=pVY[i];
last=pVY[j];
}
}
}
}
//void FindMin2(const vector<Point>&pV,int low,int high,Point &first,Point &last,float &minDis)
//{
// //二维空间寻找最小点对
// if(low==high)
// {
// minDis=FLT_MAX;
// first=last=pV[high];
// }
// else if(high==low+1)//两个顶点
// {
// minDis=Diff(pV[low],pV[high]);
// first=pV[low];
// last=pV[high];
// }
// else
// {
// int mid=(low+high)/2;
// Point lFirst,lLast,rFirst,rLast;
// float lMinDis,rMinDis;
// FindMin2(pV,low,mid,lFirst,lLast,lMinDis);
// FindMin2(pV,mid+1,high,rFirst,rLast,rMinDis);
//
// if(lMinDis<rMinDis)
// {
// minDis=lMinDis;
// first=lFirst;
// last=lLast;
// }
// else
// {
// minDis=rMinDis;
// first=rFirst;
// last=rLast;
// }
// if(pV[mid+1].x-pV[mid].x<minDis)
// {//最小距离点对才可能出现在左右半边各一个
//
// for(int l=mid;l>=low&&pV[mid+1].x-pV[l].x<minDis;l--)
// {
// for(int r=mid+1;r<=high&&pV[high].x-pV[mid].x<minDis;r++)
// {
// if(Diff(pV[l],pV[r])<minDis)
// {
//
// minDis=Diff(pV[l],pV[r]);
// first=pV[l];
// last=pV[r];
//
//
//
// }
// }
// }
// }
// }
//
//}
void RunAlgorithm()
{
vector<Point>pVX;
vector<Point>pVY;
int size;
cin>>size;
while(size)
{
pVX.clear();
pVY.clear();
Init(pVX,pVY,size);
PrintVector(pVX);
PrintVector(pVY);
//PrintVector(pV);
std::sort(pVX.begin(),pVX.end(),CompareX());//按x轴排序
std::sort(pVY.begin(),pVY.end(),CompareY());
PrintVector(pVX);
PrintVector(pVY);
Point p1,p2;
float minDis;
minDis=FLT_MAX;
Tic();
FindMin1(pVX,0,pVX.size()-1,p1,p2,minDis);
Toc();
std::cout<<"FindMin1:"<<p1<<" "<<p2<<" minDis:"<<minDis<<std::endl;
/* minDis=FLT_MAX;
Tic();
FindMin2(pV,0,pV.size()-1,p1,p2,minDis);
Toc();
std::cout<<"FindMin2:"<<p1<<" "<<p2<<" minDis:"<<minDis<<std::endl;*/
minDis=FLT_MAX;
Tic();
FindMin22(pVX,pVY,0,pVX.size()-1,p1,p2,minDis);
Toc();
std::cout<<"FindMin22:"<<p1<<" "<<p2<<" minDis:"<<minDis<<std::endl;
cin>>size;
}
}
int main()
{
RunAlgorithm();
system("pause");
return 0;
}