1

有一个具有 n 个 3d 点 (x,y,z) 的集合 A 和具有 m 个 3d 点 (x,y,z) 的集合 B。对于集合 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;
}
4

2 回答 2

2

您正在使用 O(n^2) 算法。我怀疑这是否足够快。有关加快速度的一些方法，请查看这篇文章。

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

于 2012-06-05T15:01:10.760 回答
0

一种方法是从 O(n log n) 的任一集合创建最近邻三角剖分，然后使用接近搜索之类的方法将每个点从另一个集合依次覆盖到三角剖分上以找到它的最近邻。为了在 C 中做这类事情，Joseph O'Rourkes 的书非常值得一读。

于 2012-06-05T15:28:33.003 回答