兩點之間的最短距離。蠻力算法

我應該使用brute-torce算法確定最近的點。我無法得到這個編譯。兩點之間的最短距離。蠻力算法

#include <stdio.h> 
#include <float.h> 
#include <stdlib.h> 
#include <math.h> 


struct Point 
{ 
    int x, y; 
}; 




int compareX(const void* a, const void* b) 
{ 
    Point *p1 = (Point *)a, *p2 = (Point *)b; 
    return (p1->x - p2->x); 
} 

int compareY(const void* a, const void* b) 
{ 
    Point *p1 = (Point *)a, *p2 = (Point *)b; 
    return (p1->y - p2->y); 
} 


float dist(Point p1, Point p2) 
{ 
    return sqrt((p1.x - p2.x)*(p1.x - p2.x) + 
       (p1.y - p2.y)*(p1.y - p2.y) 
      ); 
} 


float bruteForce(Point P[], int n) 
{ 
    float min = FLT_MAX; 
    for (int i = 0; i < n; ++i) 
     for (int j = i+1; j < n; ++j) 
      if (dist(P[i], P[j]) < min) 
       min = dist(P[i], P[j]); 
    return min; 
} 


float min(float x, float y) 
{ 
    return (x < y)? x : y; 
} 



float stripClosest(Point strip[], int size, float d) 
{ 
    float min = d; // Initialize the minimum distance as d 

    qsort(strip, size, sizeof(Point), compareY); 


    for (int i = 0; i < size; ++i) 
     for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j) 
      if (dist(strip[i],strip[j]) < min) 
       min = dist(strip[i], strip[j]); 

    return min; 
} 


float closestUtil(Point P[], int n) 
{ 

if (n <= 3) 
     return bruteForce(P, n); 


    int mid = n/2; 
    Point midPoint = P[mid]; 


    float dl = closestUtil(P, mid); 
    float dr = closestUtil(P + mid, n-mid); 


    float d = min(dl, dr); 


Point strip[n]; 
    int j = 0; 
    for (int i = 0; i < n; i++) 
     if (abs(P[i].x - midPoint.x) < d) 
      strip[j] = P[i], j++; 


    return min(d, stripClosest(strip, j, d)); 
} 


float closest(Point P[], int n) 
{ 
    qsort(P, n, sizeof(Point), compareX); 


    return closestUtil(P, n); 
} 


int main() 
{ 
    Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}}; 
    int n = sizeof(P)/sizeof(P[0]); 
    printf("The smallest distance is %f ", closest(P, n)); 
    return 0; 
}

來源

2013-02-12 Darius Stewart

我不能在這裏看到的問題。請至少給我們編譯錯誤。 – fsw 2013-02-12 18:21:07

請使用C編譯器進行C代碼（**上面的代碼無效C **）。（wannabe）C代碼使用C++編譯器可能會導致很難跟蹤錯誤。 – pmg 2013-02-12 18:23:41

只是正常工作，輸出爲「最小距離爲1.414214」

來源

2013-02-12 18:21:50 fons

請使用C編譯器進行C代碼（**上面的代碼不是有效的C **）。（wannabe）C代碼使用C++編譯器可能會導致很難跟蹤錯誤。 – pmg 2013-02-12 18:25:44

Point是不是有效的類型。你的意思是struct Point。

或者，你可以使用一個typedef：

typedef struct 
{ 
    int x, y; 
} Point;

來源

2013-02-12 18:23:34 netcoder

兩點之間的最短距離。蠻力算法

回答

相關問題