# closest pair algorithm

This is a discussion on closest pair algorithm within the C Programming forums, part of the General Programming Boards category; Hello Forum I'm trying to implement the closest pair algorithm but when i run it i get wrong pairs anyone ...

1. ## closest pair algorithm

Hello Forum
I'm trying to implement the closest pair algorithm but when i run it i get wrong pairs
anyone help ?
here is the code in c

Code:
```#include <stdio.h>
#include <math.h>

double getDistance (double x1,double y1, double x2, double y2)
{
return (sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)));
}

int main(){
int i,j=0;
const int NUMBER_OF_POINTS = 3;
double points[NUMBER_OF_POINTS][2];
printf ("Enter %d points: " , NUMBER_OF_POINTS );
for(i=0; i< NUMBER_OF_POINTS;i++)
scanf ("%lf", &points[i][0]);
scanf ("%lf", &points[i][1]);

int p1=0,p2=1;
double shortestDistance = getDistance( points[p1][0], points[p1][1], points[p2][0], points[p2][1]);
for ( i=0;i<NUMBER_OF_POINTS;i++){
for ( j=i+1;j<NUMBER_OF_POINTS;j++){
double distance=getDistance(points[i][0],points[i][1],points[j][0],points[j][1]);

if(shortestDistance > distance){
p1=i;
p2=j;
shortestDistance = distance;
}
}
}

printf ("The closest two points are (%lf", points[p1][0]);
printf (", %lf", points[p1][1]);
printf (") and (");
printf ("%lf", points[p2][0]);
printf (",%lf\n" ,points[p2][1]);

system("pause");
return 0;
}```

2. I used that formula recently and found that I needed to be sure I was dealing with positive distances, only.

So I used abs() around anything that gave me negative values.

Just a quick study, but I didn't see anything wrong with what's there.

3. let me give a quick example
when i input the points (1,1) , (4,2) , (5,3)
the output should be the point (4,2) , (5,3) as they are closer
but the output i take is
(1,0) , (1,0)

4. Well point 1,0 is VERY CLOSE to point 1,0, for sure.

Let me put it into the oven, see what cooks up.

I had to change a few things (working in Turbo C right now), but this works fine:
Code:
```#include <stdio.h>
#include <math.h>
#define NUMBER_OF_POINTS 3

double getDistance (double x1,double y1, double x2, double y2)
{
return (sqrt((x2-x1)* (x2-x1) + (y2-y1) *(y2-y1)));
}

int main(){
int i,j=0, p1=0,p2=1;
//	const int NUMBER_OF_POINTS = 3;
double points[NUMBER_OF_POINTS][2]={ {1,0}, {4,3}, {5,2} };
//    printf ("Enter %d points: " , NUMBER_OF_POINTS );
//	for(i=0; i< NUMBER_OF_POINTS;i++)
//	scanf ("%lf", &points[i][0]);
//    scanf ("%lf", &points[i][1]);

double shortestDistance = getDistance( points[p1][0], points[p1][1], points[p2][0], points[p2][1]);
for ( i=0;i<NUMBER_OF_POINTS;i++){
for ( j=i+1;j<NUMBER_OF_POINTS;j++){
double distance=getDistance(points[i][0],points[i][1],points[j][0],points[j][1]);

if(shortestDistance > distance){
p1=i;
p2=j;
shortestDistance = distance;
}
}
}

printf ("The closest two points are (%lf", points[p1][0]);
printf (", %lf", points[p1][1]);
printf (") and (");
printf ("%lf", points[p2][0]);
printf (",%lf)\n" ,points[p2][1]);

//system("pause");
(void) getchar();
return 0;
}```

5. Suggestion 1: Format your code so it is readable.
Suggestion 2: After reading in the point values; display then all to confirm you read them in right.
Suggestion 3: Always use braces ("{", "}") around loops.

Tim S.

6. As a way to debug, Tim's point can't be stressed enough. Test each block of code for accuracy in what you need it to do.

You can work for hours looking for a bug in your processing, only to find out it's been a bug in your earlier input function, the whole time! That's a real 4 letter word, moment!

btw, I tried 1,1 also, and it worked fine with it. Using abs() did not help or hinder here - both worked.

abs(x)*abs(x) == x*x

for anything but imaginary x.

8. Thanks, EVOEx. Obvious once you think for a sec. /facepalm

but it seems to have problems in case you want to input the cordinates of the points

10. Bingo! Nice catch. you need to add braces around the two scanf() lines of code - right now only the first one gets executed in each loop.

I'll bet that's what Tim was suggesting, don't you think so?

(I took it as a general suggestion, as well.)

11. yesssss it seems to work just fine
thanx again

12. Thank You Tim S!

You Rascal!

Popular pages Recent additions