가장 가까운 쌍이 여러 개있는 경우 가장 가까운 점 쌍을 찾습니다.

Question

다음 코드는 C++ liang 교과서로 프로그래밍 소개에서 가장 가까운 점 쌍 문제를 찾는 데 사용됩니다. 가장 가까운 쌍이 여러 개 존재하는 경우 모든 가까운 점 쌍을 찾을 수 있도록 편집하려고합니다.

#include <iostream> 
#include <cmath> 
using namespace std; 

/** Compute the distance between two points (x1, y1) and (x2, y2) */ 
double getDistance(double x1, double y1, double x2, double y2) 
{ 
    return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)); 
} 

int main() 
{ 
    const int NUMBER_OF_POINTS = 8; 

    // Each row in points represents a point 
    double points[NUMBER_OF_POINTS][2]; 

    cout << "Enter " << NUMBER_OF_POINTS << " points: "; 
    for (int i = 0; i < NUMBER_OF_POINTS; i++) 
     cin >> points[i][0] >> points[i][1]; 

    // p1 and p2 are the indices in the points array 
    int p1 = 0, p2 = 1; // Initial two points 
    double shortestDistance = getDistance(points[p1][0], points[p1][1], 
             points[p2][0], points[p2][1]); // Initialize   

    // Compute distance for every two points 
    for (int i = 0; i < NUMBER_OF_POINTS; i++) 
    { 
    for (int j = i + 1; j < NUMBER_OF_POINTS; j++) 
    { 
     double distance = getDistance(points[i][0], points[i][1], 
             points[j][0], points[j][1]); // Find distance 

     if (shortestDistance > distance) 
     { 
      p1 = i; // Update p1 
      p2 = j; // Update p2 
      shortestDistance = distance; // Update shortestDistance 
     } 
    } 
    } 

    // Display result 
    cout << "The closest two points are " << 
    "(" << points[p1][0] << ", " << points[p1][1] << ") and (" << 
    points[p2][0] << ", " << points[p2][1] << ")"; 

    return 0; 

} 

는 I 새로운 배열 거리 점을 이용하여 해결하고 새로운 배열을 통해 해당 I 루프 후에, 거리를 산출 할 때마다 포인트 쌍의 거리를 저장하고, 최단 거리를 출력하지만 나는 확실히 똑똑한 솔루션이 있다고 생각, 임 프로그래밍 : 당신은 벡터의 주식 결과에 알고리즘을 변경할 수 있습니다

double distance_points[28][5]; 
int f = 0 ; 
// Compute distance for every two points 
for (int i = 0; i < NUMBER_OF_POINTS; i++) 
{ 
    for (int j = i + 1; j < NUMBER_OF_POINTS; j++) 
    { 

     double distance = getDistance(points[i][0], points[i][1], 
             points[j][0], points[j][1]); // Find distance 
     distance_points[f][0] = distance; 
     distance_points[f][1] = points[i][0]; 
     distance_points[f][2] = points[i][1]; 
     distance_points[f][3] = points[j][0]; 
     distance_points[f][4] = points[j][1]; 
     f++; 
    } 
} 

Answer 1

에서 아주 새로운 :

std::vector<int> p1, p2; 
double shortestDistance = getDistance(points[p1][0], points[p1][1], 
            points[p2][0], points[p2][1]); // Initialize   

for (int i = 0; i < NUMBER_OF_POINTS; i++) { 
    for (int j = i + 1; j < NUMBER_OF_POINTS; j++) { 
     const double distance = getDistance(points[i][0], points[i][1], 
              points[j][0], points[j][1]); 

     if (shortestDistance >= distance) { 
      if (shortestDistance > distance) { 
       p1.clear(); 
       p2.clear(); 
       shortestDistance = distance; // Update shortestDistance 
      } 
      p1.push_back(i); // Update p1 
      p2.push_back(j); // Update p2 
     } 
    } 
}