最近对问题——分治法

问题描述：设p1=(x1,y1),p2=(x2,y2),...,pn=(xn,yn)是平面上n个点构成的集合S,设计算法找出集合S中距离最近的点对(二维平面)。

1、蛮力法：直接用欧几里得距离计算即可

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
struct In{
	double x;
	double y;
}p[500];
int main(){
	int n;
	double min,d;
	double x1,y1,x2,y2;
	printf("输入n:\n");
	scanf("%d",&n);
	printf("输入%d个点：\n",n);
	for(int i=0;i<n;i++)
    scanf("%lf%lf",&p[i].x,&p[i].y);
	min=pow((p[0].x-p[1].x),2)+pow((p[0].y-p[1].y),2);
	x1=p[0].x;y1=p[0].y;
	x2=p[1].x;y2=p[1].y;
	for(int i=1;i<n-1;i++)
	for(int j=i+1;j<n;j++){
		d=pow((p[i].x-p[j].x),2)+pow((p[i].y-p[j].y),2);
		if(min>d){
		   min=d;
		   x1=p[i].x;y1=p[i].y;
		   x2=p[j].x;y2=p[j].y;
		}
	}
	printf("输出最近对的距离：\n%lf\n",sqrt(min));
	printf("输出最近对的两个点：\n(%lf,%lf)与(%lf,%lf)\n",x1,y1,x2,y2);
}
/*
5
85.1 52.1 65 85.6 12.6 5.2 2.1 6.1 3 9.64
*/

2、分治法

算法效率取决于划分点m的选取，要遵循平衡子问题的原则；

思想：点（x，y）

首先对所有点s按照x坐标升序排列，选取m为x的中位数；

Closepoints(s):

若只有一个点，return inf;

若只剩两个点，return 欧几里得距离；

若剩下三个点，分别计算两两点距离，比较三个中的最小值，将其返回；

      构造集合s1,s2；使得s1为x坐标小于m，s2为x坐标大于m；

      递归：d1=ClosePoints(s1);d2=ClosePoints(s2);

      d=min(d1,d2);

      构造集合p1,p2；p1为m减s1中点的x坐标的差值不超过d，p2为s2中点的x坐标减m的差值不超过d；

      对p1,p2按照y坐标升序排列；

      对于p1中每一个点，找出其y坐标与p2中点的y坐标差值不超过d的点，计算两点距离为dp；

      return min(d,dp);

注意：p1 p2点因 鸽舍原理 点不会超过6个（有说8个的）

#include<stdio.h>
#include<stdlib.h> 
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;

/*递归中慎用全局变量（若这些变量涉及到递归传参）*/

struct In{
	double x;
	double y;
};
int cmp(const void *a,const void *b){
	return (*(In*)a).x - (*(In*)b).x;
}
int cmp1(const void*a,const void*b){
	return (*(In*)a).y>(*(In*)b).y?1:-1;
}
double ClosePoint(In s[],int n,In f[]){
	int i,j=0,k=0,t,flag,nk;
	double d1,d2,d,di,dt,m;
    struct In p1[100],p2[100],s1[300],s2[300];
	struct In t1[2],t2[2];
	if(n==1)return 20000;//inf无限大 一个点 
	if(n==2){//两个点 
		f[0]=s[0];f[1]=s[1];
		d=pow(s[0].x-s[1].x,2)+pow(s[0].y-s[1].y,2);
		return d;
	}
	if(n==3){//三个点
		d=pow(s[0].x-s[1].x,2)+pow(s[0].y-s[1].y,2);
		d1=pow(s[0].x-s[2].x,2)+pow(s[0].y-s[2].y,2);
		d2=pow(s[2].x-s[1].x,2)+pow(s[2].y-s[1].y,2);
		if((d<d1)&&(d<d2)){
			f[0]=s[0];f[1]=s[1];
			return d;
		}
		else if(d1<d2){
			f[0]=s[0];f[1]=s[2];
			return d1;
		}
		else {//if((d2<d)&&(d2<d1))
			f[0]=s[2];f[1]=s[1];
			return d2;
		}
	} 
	
	if(n%2==1) m=s[n/2].x;
	else m=(s[n/2].x+s[n/2-1].x)/2;
    
    for(i=0;(i<=n/2)&&(s[i].x<m);i++)
    s1[i]=s[i];  
    flag=i;
    for(t=0;i<n;i++)
    if(s[i].x>m)s2[t++]=s[i];

	d1=ClosePoint(s1,flag,f);
	t1[0]=f[0];t1[1]=f[1];//记录最短距离的位置 
	d2=ClosePoint(s2,t,f);
	t2[0]=f[0];t2[1]=f[1];
	if(d1<d2){
		d=d1;
		f[0]=t1[0];
		f[1]=t1[1];
	}
	else {
		d=d2;
		f[0]=t2[0];
		f[1]=t2[1];
	}
	
	i=flag-1;
	while(m-s1[i].x<d)
	p1[j++]=s1[i--];//不需要分别x y赋值 p[j].x=s[i].x; 
	i=0;
	while(s2[i].x-m<d)
	p2[k++]=s2[i++];
	
    qsort(p1,j,sizeof(p1[0]),cmp1);
    qsort(p2,k,sizeof(p2[0]),cmp1);
    
    di=d;
	for(i=0;i<j;i++)
	for(t=0;t<k;t++){
		if(fabs(p1[i].y-p2[t].y)<d){
			dt=pow(p1[i].x-p2[t].x,2)+pow(p1[i].y-p2[t].y,2);
			if(dt<di){
				di=dt;
				f[0]=p1[i];
				f[1]=p2[t];
			}
		}	
	}
	return di;
}
int main(){
  	int n;
	double min,d,m;
	double x1,y1,x2,y2;	
    struct In s[500],f[2];  
	printf("输入n:\n");
	scanf("%d",&n);
	printf("输入%d个点：\n",n);
	for(int i=0;i<n;i++)
    scanf("%lf%lf",&s[i].x,&s[i].y);
    qsort(s,n,sizeof(s[0]),cmp);
	d=ClosePoint(s,n,f);
	printf("\n(%f,%f) (%f,%f)\n",f[0].x,f[0].y,f[1].x,f[1].y);
	d=pow(f[0].x-f[1].x,2)+pow(f[0].y-f[1].y,2);
	printf("\nd=%f\n",sqrt(d));
	return 0;
}
/*
5
85.1 52.1 65 85.6 12.6 5.2 2.1 6.1 3 9.64
4
2 2 1.5 2 6 2 3.1 2
6
20.1 3.2 15.6 23.1 60 2.1 5.6 2.3 63.0 41 52.3 12.69

*/