User will enter the number of points and the co ordinates . Answer should be the minimum distance which will be the distance between the closest pair of points.I have also used the clock function to obtain total elapsed time.. is there any problem in its syntax?
What I have tried:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<float.h>
struct Point
{
int x, y;
};
typedef struct Point Point;
int compareX(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->x - p2->x);
}
int compareY(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->y - p2->y);
}
float dist(Point p1, Point p2)
{
return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +
(p1.y - p2.y)*(p1.y - p2.y)
);
}
float minm(float x, float y)
{
return (x < y)? x : y;
}
float stripClosest(Point strip[], int n, float d)
{
float minm = d;
int i,j;
for ( i = 0; i < n; ++i)
for (j = i+1; j < n && (strip[j].y - strip[i].y) < minm; ++j)
if (dist(strip[i],strip[j]) < minm)
minm = dist(strip[i], strip[j]);
return minm;
}
float closestUtil(Point Px[], Point Py[], int n)
{
int mid = n/2;
Point midPoint = Px[mid];
Point Pyl[mid+1];
Point Pyr[n-mid-1];
int li = 0, ri = 0,i;
for (i = 0; i < n; i++)
{
if (Py[i].x <= midPoint.x)
Pyl[li++] = Py[i];
else
Pyr[ri++] = Py[i];
}
float dl = closestUtil(Px, Pyl, mid);
float dr = closestUtil(Px + mid, Pyr, n-mid);
float d = minm(dl, dr);
Point strip[n];
int j = 0;
for ( i = 0; i < n; i++)
if (abs(Py[i].x - midPoint.x) < d)
strip[j] = Py[i], j++;
return minm(d, stripClosest(strip, j, d) );
}
float closest(Point P[], int n)
{
Point Px[n];
Point Py[n];
int i;
for ( i = 0; i < n; i++)
{
Px[i] = P[i];
Py[i] = P[i];
}
qsort(Px, n, sizeof(Point), compareX);
qsort(Py, n, sizeof(Point), compareY);
return closestUtil(Px, Py, n);
}
int main()
{
clock_t start,last;
double total;
FILE *fp;
int n,i;
printf("Enter number of co ordinates:\n");
scanf("%d",&n);
Point P[n];
printf("Enter the co ordinates:\n");
for(i=0;i<n;i++)
scanf("%d %d",&P[i].x,&P[i].y);
start=clock();
printf("Minimum distance is %f", closest(P, n));
last=clock();
total=(double)(last-start);
printf("%f",total);
return 0;
}