집합 A의 점에서 집합 B의 점까지의 최단 거리를 찾는 알고리즘

n 개의 3d 점 (x, y, z)가있는 집합 A와 m 개의 3d 점 (x, y, z)을 갖는 B 집합이 있습니다. 집합 A의 각 점 (Xi, Yi, Zi)에 대해 (Xi, Yi, Zi)로부터 최소 거리를 가진 집합 B에서 점을 찾아야합니다.집합 A의 점에서 집합 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; 
}

출처

2012-06-05 hell coder

주어진 시간 제한은 무엇입니까 ?? – james

[점 알고리즘 간의 최단 거리] (http://stackoverflow.com/questions/1602164/shortest-distance-between-points-algorithm)를보십시오. – JAB

자세한 내용을 입력하십시오. 코드에 결함이 있으며 무한 루프가 발생합니까? 아니면 더 작은 데이터 세트에서 작동하며 더 큰 데이터 세트에 너무 많은 시간이 걸립니다. – mbeckish

O (n^2) 알 고를 사용 중입니다. 나는 그것이 충분히 빠르다는 것을 의심한다. 더 빨리 수행 할 수있는 방법은 this article을 확인하십시오.

더 구체적으로 말하면, 재귀에 익숙하다면이 기사에서 설명한 정복 접근법을 비교적 쉽게 사용할 수 있습니다. z 축을 다루고 있기 때문에 2 개의 분할 선 (x 축은 하나, y는 하나)을 사용하기 위해 거기에 설명 된 알고리즘을 확장해야하므로 좀 더 복잡해집니다.

출처

2012-06-05 15:01:10 dcp

괜찮습니다. 그 기사가 도움이된다. 고맙습니다. :) –

하나의 접근법은 O (n log n) 인 세트에서 nearest neighbour triangulation을 생성 한 다음 proximity search과 같은 것을 사용하여 다른 세트의 각 포인트를 삼각 측량에 차례로 드레이핑하여 가장 가까운 이웃을 찾습니다. C에서 이런 종류의 일을하는 경우, Joseph O'Rourkes book은 읽을만한 가치가 있습니다.

출처

2012-06-05 15:28:33

집합 A의 점에서 집합 B의 점까지의 최단 거리를 찾는 알고리즘

답변

관련 문제