Anonymous user
Talk:Closest-pair problem/C: Difference between revisions
→Propose replacing code: clean up a bit
(→Propose replacing code: new section) |
(→Propose replacing code: clean up a bit) |
||
Line 16:
typedef struct { double x, y; } point_t, *point;
/* note: even though l_list and r_list are used by each recursion of closest(),
they are always used in
int *l_list, *r_list;
Line 32:
double brute_force(point pts, int max_n,
{
int i, j;
point pi;
double d,
for (i = 0, pi = pts; i < max_n; pi++, i++) {
for (j = i + 1; j < max_n; j++) {
if (d >= min_d )
*b = j;▼
}
}
return
}
Line 64 ⟶ 65:
double min_d, d, dsqrt, median;
/*
if (n
if (n == 3) {▼
}▼
/* get left and right results */
left = right = n / 2;
min_d = d;
*a = a1;
Line 98 ⟶ 82:
dsqrt = sqrt(min_d);
/* find points within +- min distance on X from the center line,
for ( lsize = 0, left--;
median - pts[left].x < dsqrt && left;
Line 142 ⟶ 127:
int main(int argc, char **argv)
{
int i
point a, b;
Line 155 ⟶ 139:
}
/*
▲ d = brute_force(pts, NP, &i, &j);
printf("brute force: %g,
printf("between (%f,%f) and
*/
int cmp_x(const void *a, const void *b) {
| |||