第一题
分治：点对最短距离
要求：求平面上距离最近的点间的距离
思路参照了一篇解释的非常优秀的博客：
[寻找距离最小的平面点对——分治方法]（https://blog.csdn.net/qq_40707370/article/details/85268256
）
其中的分治思想就是：每次把n个点分成两份，最短距离dm一定出现在左边n/2个点的最短距离d1，右边n/2个点的最短距离d2，左右配对的最短距离d3这三个值之间，其中最后一个要是穷举的话，会有n/2*n/2=n^2/4种组合,于是想要减少配对的可能，就是对于一边的点来说，可能出现最短距离的点只会在一个宽n/2,长n/2的矩形内，而且这个点必须和作为划分的midX的距离不超过min(d1,d2),于是就可以减小问题规模。
上面的博客+书上有一些要求，代码里没有实现：
1.为了平衡问题规模其实最好应取中位数
（我每次取的平均数）
2.确定好x属于左边的区域[midX-dm,minX],应依次对这个里面的点，检查右侧[midX,midX+dm]内的点是否符合情况
（我直接把横坐标在[midX-dm,midX+dm]的k个点全部存入辅助数组，写了个O(n)=n^2二重循环）
还有一点不足是：开了三个大数组，以为会超时超内存，万幸的是过了
因为老师不允许用快排，使用了MergeSort，没想到上学期学的东西很快就忘了，一开始就被卡在这里，同样参照了一篇博客：
[C语言 归并排序]（https://www.cnblogs.com/942267027wzmblog/p/6882267.html
）
总的来说：一个负责分，一个负责连接，因为怕出错，就直接定义了一个全局的数组
代码如下：
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
class St{
public:
double x;
double y;
};
St Site[100000];
St Temp[100000];
St Add[100000];
double CalDis(St M,St N)
{
double dx=M.x-N.x;
double dy=M.y-N.y;
return sqrt(dx*dx+dy*dy);
}
void MergeAdd_X(St A[],int left,int mid,int right,St T[])
{
int i=left;
int j=mid+1;
int k=left;
while(i<=mid&&j<=right)
{
if(A[i].x<=A[j].x)
{
T[k].x=A[i].x;
T[k].y=A[i].y;
k++;
i++;
}
else
{
T[k].x=A[j].x;
T[k].y=A[j].y;
k++;
j++;
}
}
while(i<=mid)
{
T[k].x=A[i].x;
T[k].y=A[i].y;
k++;
i++;
}
while(j<=right)
{
T[k].x=A[j].x;
T[k].y=A[j].y;
k++;
j++;
}
for(int f=left;f<k;f++)
{
A[f].x=T[f].x;
A[f].y=T[f].y;
}
}
void MergeAdd_Y(St A[],int left,int mid,int right,St T[])
{
int i=left;
int j=mid+1;
int k=left;
while(i<=mid&&j<=right)
{
if(A[i].y<=A[j].y)
{
T[k].x=A[i].x;
T[k].y=A[i].y;
k++;
i++;
}
else
{
T[k].x=A[j].x;
T[k].y=A[j].y;
k++;
j++;
}
}
while(i<=mid)
{
T[k].x=A[i].x;
T[k].y=A[i].y;
k++;
i++;
}
while(j<=right)
{
T[k].x=A[j].x;
T[k].y=A[j].y;
k++;
j++;
}
for(int f=left;f<k;f++)
{
A[f].x=T[f].x;
A[f].y=T[f].y;
}
}
void MergeSort(St A[],int left,int right,St T[],bool flag)
{
if(flag) //对X排序
{
if(left<right)
{
int mid=(left+right)/2;
MergeSort(A,left,mid,T,flag);
MergeSort(A,mid+1,right,T,flag);
MergeAdd_X(A,left,mid,right,T);
}
}
else
{
if(left<right) //对Y排序
{
int mid=(left+right)/2;
MergeSort(A,left,mid,T,flag);
MergeSort(A,mid+1,right,T,flag);
MergeAdd_Y(A,left,mid,right,T);
}
}
}
double MIN(double a,double b)
{
return a<b?a:b;
}
double FindAns(St A[],int left,int right,St T[])
{
if(right-left==0)
{
return -100000.0;
}
else if(right-left==1)
{
return CalDis(A[left],A[right]);
}
else if(right-left==2)
{
double d1=CalDis(A[left],A[left+1]);
double d2=CalDis(A[left+1],A[right]);
double d3=CalDis(A[left],A[right]);
double dm=0.0;
dm=MIN(d1,d2);
dm=MIN(dm,d3);
return dm;
}
else
{
int mid=(left+right)/2;
double dm=0.0;
double d1=FindAns(A,left,mid,T);
double d2=FindAns(A,mid+1,right,T);
dm=MIN(d1,d2);
int i=left;
int j=right;
int k=0;
for(i=mid;i>=left;i--)
{
double t=fabs(A[i].x-A[mid].x);
if(t<=dm)
{
T[k].x=A[i].x;
T[k].y=A[i].y;
k++;
}
else
{
break;
}
}
for(int i=mid+1;i<=right;i++)
{
double t=fabs(A[i].x-A[mid].x);
if(t<=dm)
{
T[k++]=A[i];
}
else
break;
}
MergeSort(T,0,k-1,Add,0);
for(i=0;i<k;i++)
{
for(j=i+1;j<k;j++)
{
if(fabs(T[i].y-T[j].y)<dm)
{
double op=CalDis(T[i],T[j]);
dm=MIN(op,dm);
}
else
break;
}
}
return dm;
}
}
int main()
{
int n;
while(scanf("%d",&n)!=0&&n!=0)
{
double a,b;
for(int i=0;i<n;i++)
{
scanf("%lf %lf",&a,&b);
Site[i].x=a;
Site[i].y=b;
}
MergeSort(Site,0,n-1,Temp,1); //pre sort by x
double dm=FindAns(Site,0,n-1,Temp);
dm=dm/2; //Required by the task need the half of the smallest distence
printf("%.2lf\n",dm);
}
return 0;
}
中间遇到的坑：
1、归并排序搞错，老老实实写了一维，然后二维，检验通过了才往后写
2、一开始没想清流程，何时对x,y排序，现筛出x再对y排序还是反过来，归并排序要写几个，d1,d2,d3求的顺序、递归要怎么写
3、没想出如何求d3，二重循环都没想到
4、辅助数组没想到要用两个，没想到把符合要求的x要存进辅助数组，有点混乱
5、各种小问题，i,j写反，赋值左右两边写反
6、甚至忘了怎么写输入0停止
写了两天，被自己菜哭T T
