Databases
StackOverflow2013
Postsdbo
POIssue with implementing "Closest pair of points" in C++
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIssue with implementing "Closest pair of points" in C++
    primarykey
    data
    text
    <p>I'm trying to implement Closest pair of points in C++ according to Cormen book and wikipedia article, I think that algorithm is correct, but it does work only for a very small data. Code is below:</p> <pre><code>#include &lt;cstdio&gt; #include &lt;algorithm&gt; #include &lt;cmath&gt; #define REP(i,n) for(int i=0;i&lt;n;i++) using namespace std; struct point { long long x, y; }; struct dist { long long x_1,y_1,x_2,y_2, distance; } dis; inline bool OrdX(const point &amp;a, const point &amp;b) { if(a.x==b.x) { return a.y&lt;b.y; } return a.x&lt;b.x; } inline int OrdY(const point &amp;a, const point &amp;b) { if(a.y==b.y) { return a.x&lt;b.x; } return a.y&lt;b.y; } // is - function that check is a an element of X_L array inline bool is(const point &amp;a, point *X_L, int p, int k) { if(p&lt;=k) { int center = (p+k)/2; if(X_L[center].x == a.x) { return true; } if(X_L[center].x &gt; a.x) { return is(a, X_L, p, center-1); } else { return is(a, X_L, center+1, k); } } return false; } // odl - function takes two points and return distance between them ^2 inline long long odl(const point &amp;a, const point &amp;b) { return ((a.x-b.x)*(a.x-b.x))+((a.y-b.y)*(a.y-b.y)); } int tmp; // fun - function that returns the pair of closest points using divide &amp; conquer struct dist fun(int n, point *X, point *Y) { // if there are less that 4 points - it checks it using bruteforce if(n&lt;4) { if(odl(X[0], X[1]) &lt; dis.distance) { dis.distance = odl(X[0],X[1]); dis.x_1 = X[0].x; dis.y_1 = X[0].y; dis.x_2 = X[1].x; dis.y_2 = X[1].y; } if(n==3) { if(odl(X[0], X[2]) &lt; dis.distance) { dis.distance = odl(X[0],X[2]); dis.x_1 = X[0].x; dis.y_1 = X[0].y; dis.x_2 = X[2].x; dis.y_2 = X[2].y; } if(odl(X[1], X[2]) &lt; dis.distance) { dis.distance = odl(X[1],X[2]); dis.x_1 = X[1].x; dis.y_1 = X[1].y; dis.x_2 = X[2].x; dis.y_2 = X[2].y; } } } // otherwise it divides points into two arrays and runs fun // recursively foreach part else { int p=n/2; int PPP = (X[p].x + X[p-1].x)/2; point *X_L = new point[p]; point *X_R = new point[n-p]; point *Y_L = new point[p]; point *Y_R = new point[n-p]; REP(i,p) X_L[i] = X[i]; for(int r=p; r&lt;n; r++) { X_R[r-p] = X[r]; } int length_Y_L = 0; int length_Y_R = 0; REP(i,n) { if(is(Y[i], X_L, 0, p)) { Y_L[length_Y_L++] = Y[i]; } else { Y_R[length_Y_R++] = Y[i]; } } dist D_L = fun(p, X_L, Y_L); dist D_R = fun(n-p, X_R, Y_R); dist D; if(D_L.distance &lt; D_R.distance) { D = D_L; } else { D = D_R; } tmp = 0; point *Y2 = new point[n]; double from = sqrt((double)D.distance); for(int r=0; r&lt;n; r++) { if(Y[r].x &gt; (long long)PPP-from &amp;&amp; Y[r].x &lt; (long long)PPP + from) { Y2[tmp++] = Y[r]; } } //--tmp; //int xxx = min(7, tmp-r); int r = 0; for(int j=1; j&lt;min(7, tmp-r); j++) { if(odl(Y2[r], Y2[r+j]) &lt; D.distance) { D.distance = odl(Y2[r], Y2[r+j]); D.x_1 = Y2[r].x; D.y_1 = Y2[r].y; D.x_2 = Y2[r+j].x; D.y_2 = Y2[r+j].y; } r++; } dis = D; } return dis; } int main() { int n; n = 7; point *X = new point[n]; point *Y = new point[n]; for(int i=0; i&lt; 7; i++) { X[i].x = 0; X[i].y = 10*i; } /* REP(i,n) { scanf("%lld %lld", &amp;X[i].x, &amp;X[i].y); } */ sort(X, X+n, OrdX); REP(i,n) Y[i] = X[i]; sort(Y, Y+n, OrdY); dis.distance = odl(X[0], X[1]); dis.x_1 = X[0].x; dis.y_1 = X[0].y; dis.x_2 = X[1].x; dis.y_2 = X[1].y; dist wynik = fun(n, X, Y); printf(" %lld %lld\n %lld %lld\n", wynik.x_1, wynik.y_1, wynik.x_2, wynik.y_2); return 0; } </code></pre> <p>and I get this error:</p> <pre><code> malloc.c:3096: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &amp;((av)-&gt;bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) &amp;&amp; old_size == 0) || ((unsigned long) (old_size) &gt;= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) &amp; ~((2 * (sizeof(size_t))) - 1))) &amp;&amp; ((old_top)-&gt;size &amp; 0x1) &amp;&amp; ((unsigned long)old_end &amp; pagemask) == 0)' failed. </code></pre> <p>I've tried loooking for explanation of this error but can't find anything clear for me :/. Can You please help me to solve this ? Thanks</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USConrad
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POIssue with implementing "Closest pair of points" in C++
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. POIssue with implementing "Closest pair of points" in C++
      1. This table or related slice is empty.
      1. VTDownMod
    3. VO
      singulars
      1. POIssue with implementing "Closest pair of points" in C++
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThat's a nice wall of code you got there. Care to format it for us?
      singulars
      1. POIssue with implementing "Closest pair of points" in C++
      1. USsehe
    2. COAt the fourth line I think "This code is so bad, would I have to maintain it, I'd rather write it anew over the weekend." And thus endedth my attempt at answering your question.
      singulars
      1. POIssue with implementing "Closest pair of points" in C++
      1. USsbi
    3. COMixed C/C++ idiom... Linus was right! BTW: a global variable named "tmp" won't win you the beauty-award.
      singulars
      1. POIssue with implementing "Closest pair of points" in C++
      1. USwildplasser
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload