1

n 個の 3d ポイント (x,y,z) を持つセット A と m 個の 3d ポイント (x,y,z) を持つセット B があります。集合 A の各点 (Xi,Yi,Zi) に対して、(Xi,Yi,Zi) からの距離が最小になる集合 B の点を見つける必要があります。

私のコードは、指定された制限時間を使い果たしています。助けてください。

#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 軸に 1 つ、次に y に 1 つ) を使用する必要があるため、もう少し複雑になります。

于 2012-06-05T15:01:10.760 に答える
0

1 つのアプローチは、O(n log n) であるいずれかのセットから最近傍三角形分割を作成し、近接検索のようなものを使用して、他のセットから三角形分割に各ポイントを順番にドレープして、最近傍を見つけることです。この種のことを C で行うには、Joseph O'Rourke の本を読む価値があります。

于 2012-06-05T15:28:33.003 に答える