Anonymous user
Talk:Closest-pair problem/C: Difference between revisions
→Propose replacing code: clean up, removed unneeded "optimizations"
(→Propose replacing code: clean up a bit) |
(→Propose replacing code: clean up, removed unneeded "optimizations") |
||
Line 18:
/* note: even though l_list and r_list are used by each recursion of closest(),
they are always used in sequentially, no need to allocate them repeatedly */
inline double dist(point a, point b)
Line 35:
{
int i, j;
double d, min_d = MAXDOUBLE;
for (i = 0
for (j = i + 1; j < max_n; j++) {
d = dist(
if (d >= min_d ) continue;
▲ *a = pi;
*b = pts + j;
min_d = d;
Line 51 ⟶ 49:
}
void sort_y(point
{
int cmp_y(const void *a, const void *b) {
return cmp_dbl(
}
qsort(list, n, sizeof(
}
Line 62 ⟶ 60:
{
int left, right, lsize, rsize, i;
point
double min_d, d, dsqrt, median;
Line 83 ⟶ 81:
/* find points within +- min distance on X from the center line,
list their
for ( lsize = 0, left--;
median - pts[left].x < dsqrt && left;
l_list[lsize++] = pts + left--);
for ( rsize = 0;
pts[right].x - median < dsqrt && right < n;
r_list[rsize++] = pts + right++);
/* sort the
sort_y(
sort_y(
/* climb up left and right list and compare distance */
for (left = right = 0; left < lsize; left ++) {
/* next point in left list */
/* climb up right list until the y is not too low */
while (right < rsize && median > dsqrt +
right++;
Line 110 ⟶ 107:
for (i = right; i < rsize; i++) {
/* right y is too high, break */
if (
if (min_d > (d = dist(
*a =
*b =
min_d = d;
dsqrt = sqrt(min_d);
Line 131 ⟶ 128:
point pts = malloc(sizeof(point_t) * NP);
l_list = malloc(sizeof(
r_list = malloc(sizeof(
for(i = 0; i < NP; i++) {
| |||