@Gene - Cool algorithm! I tried before in java and messed a little to get exact output format. Just wondering how you came up with simple yet working code?
-Carol On Thu, Dec 22, 2011 at 6:08 PM, Gene <[email protected]> wrote: > The simplest algorithm is probably to check each point against all > others while maintaining a list of the top 3. Since 3 is a small > number, you can just maintain the top 3 in sorted order by insertion. > For a bigger K top-K you'd use a max heap. > > This can also be done in O(n log n) time by building the right data > structure. A kd-tree would be O(n log n) on random data, for example. > > The simple algorithm would code this way: > > #include <stdio.h> > > #define N_PTS 1000 > #define N_TOP 3 > > struct pt_s { int id; double x, y; } pts[N_PTS]; > > struct top_s { struct pt_s pt; double d2; } tops[N_TOP]; > > int n_top = 0; > > void clear() { n_top = 0; } > > void check_and_add(struct pt_s *hub, struct pt_s *sat) > { > double dx = hub->x - sat->x; > double dy = hub->y - sat->y; > double d2 = dx * dx + dy * dy; > struct top_s top = { *sat, d2 }; > if (n_top < 3) { // must insert somewhere > int i = n_top++; > while (i > 0 && d2 < tops[i - 1].d2) { > tops[i] = tops[i - 1]; > i--; > } > tops[i] = top; > } > else if (d2 < tops[N_TOP - 1].d2) { // may insert > int i = N_TOP - 1; > while (i > 0 && d2 < tops[i - 1].d2) { > tops[i] = tops[i - 1]; > --i; > } > tops[i] = top; > } > } > > void print(struct pt_s *hub) > { > int i; > printf("%d %d", hub->id, tops[0].pt.id); > for (i = 1; i < n_top; i++) > printf(",%d", tops[i].pt.id); > printf("\n"); > } > > int main(void) > { > int n = 0, id, i, j; > double x, y; > > while (n < N_PTS && scanf("%d%lf%lf", &id, &x, &y) == 3) { > struct pt_s pt = { id, x, y }; > pts[n++] = pt; > } > for (i = 0; i < n; i++) { > clear(); > for (j = 0; j < n; j++) > if (j != i) > check_and_add(pts + i, pts + j); > print(pts + i); > } > return 0; > } > > > On Dec 21, 1:00 am, SAMMM <[email protected]> wrote: > > You are given a list of points in the plane, write a program that > > outputs each point along with the three other points that are closest > > to it. These three points ordered by distance. > > The order is less then O(n^2) . > > > > For example, given a set of points where each line is of the form: ID > > x-coordinate y-coordinate > > > > 1 0.0 0.0 > > 2 10.1 -10.1 > > 3 -12.2 12.2 > > 4 38.3 38.3 > > 5 79.99 179.99 > > > > Your program should output: > > > > 1 2,3,4 > > 2 1,3,4 > > 3 1,2,4 > > 4 1,2,3 > > 5 4,3,1 > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
