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.
