c - 查找从集合 A 中的点到集合 B 中的点的最短距离的算法

Question

有一个集合 A 有 n 个 3d 点 (x,y,z) 和集合 B 有 m 个 3d 点 (x,y,z)。对于集合 A 中的每个点 (Xi,Yi,Zi)，我们必须在集合 B 中找到与 (Xi,Yi,Zi) 距离最小的点。

我的代码用完了给定的时间限制。请帮忙。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
long long np[50000][3],qp[50000][3];
int main()
{
long long n,q,i,j,d,ans,min;
scanf("%lld",&n);
for(i=0;i<n;i++)
    scanf("%lld%lld%lld",&np[i][0],&np[i][0],&np[i][2]);
scanf("%lld",&q);
for(i=0;i<q;i++)
scanf("%lld%lld%lld",&qp[i][0],&qp[i][1],&qp[i][2]);
for(i=0;i<q;i++)
{
    ans=0;
    min=((qp[i][0]-np[0][0])*(qp[i][0]-np[0][0]))+((qp[i][1]-np[0][1])*(qp[i][1]-qp[0][1]))+((qp[i][2]-np[0][2])*(qp[i][2]-np[0][2]));
    for(j=0;j<n;j++)
    {
        d=((qp[i][0]-np[j][0])*(qp[i][0]-np[j][0]))+((qp[i][1]-np[j][1])*(qp[i][1]-qp[j][1]))+((qp[i][2]-np[j][2])*(qp[i][2]-np[j][2]));
        if(d<min)
        {
            ans=j;
            min=d;
        }
    }
    printf("%lld\n",ans);
}
return 0;
}

Answer 1

您正在使用 O(n^2) 算法。我怀疑这是否足够快。有关更快地完成此操作的一些方法，请查看 this article .

或者更具体地说，您可以使用那篇文章中描述的分而治之的方法，如果您熟悉递归，这种方法相对简单。由于您正在处理 z 轴，因此您必须扩展那里描述的算法以使用 2 条分界线(一条用于 x 轴，然后一条用于 y)，因此它会有点复杂。