//============================================================================ // Name : 11寻找最近点对.cpp // Author : // Version : // Copyright : Your copyright notice // Description : Hello World in C++, Ansi-style //============================================================================ #include <iostream> #include<math.h> using namespace std; const int MAX=100000; class Point { public: int x; int y; Point(int X=0,int Y=0):x(X),y(Y){} }; double diff(Point a,Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } //解法二 int paration(int low,int high,Point *a) { int par=a[low].x; int par1=a[low].y; while(low<high) { while(low<high&&a[high].x>=par) high--; a[low].x=a[high].x; a[low].y=a[high].y; while(low<high&&a[low].x<=par) low++; a[high].y=a[low].y; a[high].x=a[low].x; } a[low].x=par; a[low].y=par1; return low; } void quicksort(int low,int high,Point *a) { if(low<high) { int par=paration(low,high,a); quicksort(low,par-1,a); quicksort(par+1,high,a); } } void sort(Point *a,int length) { quicksort(0,length-1, a); } double findMin( Point *a,const int length,Point &first,Point&last) { sort(a,length); double min=MAX; double dis; for(int i=0;i<length-1;i++) { dis=diff(a[i],a[i+1]); if(dis<min) { min=dis; first=a[i]; last=a[i+1]; } } return min; } //解法2 double dinfMin2(Point *a,int low,int high,Point &first,Point&last) { if(low<high) { int par=paration(low,high,a); //cout<<"par is "<<par<<endl; double min1=dinfMin2(a,low,par,first,last); double min2=dinfMin2(a,par+1,high,first,last); //cout<<"min1 is "<<min1<<" min2 is "<<min2<<endl; double min=(min1<min2)?min1:min2; // cout<<"min is " <<min<<endl; int temp[100]; int temp1[100]; memset(temp,0,sizeof(temp)); memset(temp1,0,sizeof(temp1)); int number=0; int number1=0; for(int i=low;i<=high;i++ ) { if(a[i].x>=a[par].x-min&&a[i].x<=a[par].x) { temp[number++]=i; } if(a[i].x>a[par].x&&a[i].x<=a[par].x+min) { temp1[number1++]=i; } } double min11=MAX; double dis; for(int i=0;i<number;i++) { for(int j=0;j<number1;j++) { if(abs(a[temp[number]].y-a[temp1[number1]].y)<=min) { dis=diff(a[i],a[i+1]); if(dis<min) { min11=dis; first=a[i]; last=a[i+1]; } } } } min=min<min11?min:min11; return min; } return MAX; } //扩展1 如果给定一个数组，找出相邻两个数的最大差值. class MinMAx { public: int min; int max; MinMAx(int Min=MAX,int Max=-MAX):min(Min),max(Max){} }; int findMaxDistance1(int *a,const int length) { if(!a||!length) throw new string("invalid input"); int max=a[0]; int min=a[0]; for(int i=1;i<length;i++) { if(max<a[i]) max=a[i]; if(min>a[i]) min=a[i]; } int lence=(max-min)/(length-1); int len=(max-min)/lence; MinMAx *buffer=new MinMAx[len+1]; for(int i=0;i<length;i++) { //cout<<a[i]<<" "<<(a[i]-min)/lence<<endl; if(buffer[(a[i]-min)/lence].min>a[i]) { buffer[(a[i]-min)/lence].min=a[i]; } if(buffer[(a[i]-min)/lence].max<a[i]) { buffer[(a[i]-min)/lence].max=a[i]; } } max=-MAX; for(int i=0;i<len;) { int temp=i; i++; while(i<len&&buffer[i].min==MAX&&buffer[i].max==-MAX) i++; if(buffer[i].min-buffer[temp].max>max) max=buffer[i].min-buffer[temp].max; } return max; } int main() { Point a[10]={Point(2,5),Point(3,5),Point(4,7),Point(1,7),Point(8,3),Point(9,1)}; int length=6; Point first; Point last; cout << dinfMin2(a,0,length-1,first,last)<<endl; cout<<first.x<<" "<<first.y<<endl; cout<<last.x<<" "<<last.y<<endl; int b[10]={2,5,-100,9,4,8,23}; int length1=7; cout<<findMaxDistance1(b, length1)<<endl; return 0; }
