Click here to Skip to main content
15,888,256 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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>

// A structure to represent a Point in 2D plane
struct Point
{
    int x, y;
};
typedef struct Point Point;


// Needed to sort array of points according to X coordinate
int compareX(const void* a, const void* b)
{
    Point *p1 = (Point *)a,  *p2 = (Point *)b;
    return (p1->x - p2->x);
}
// Needed to sort array of points according to Y coordinate
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;  // Initialize the minimum distance as 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)
{

    // Find the middle point
    int mid = n/2;
    Point midPoint = Px[mid];


    
    Point Pyl[mid+1];   // y sorted points on left of vertical line
    Point Pyr[n-mid-1];  // y sorted points on right of vertical line
    int li = 0, ri = 0,i;  // indexes of left and right subarrays
    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;
}
Posted
Updated 23-Jan-17 10:08am

Have you tried running this with a debugger? That should be able to easily narrow where in the code you're going wrong.

How to Debug C Program using gdb in 6 Simple Steps[^]
 
Share this answer
 
C++
Point P[n];

This is not a proper declaration of a dynamic array.
You need to use a pointer and malloc.
You need to learn properly the language.
-----
Here is links to references books on C by the authors of the language.
The C Programming Language - Wikipedia, the free encyclopedia[^]
https://hassanolity.files.wordpress.com/2013/11/the_c_programming_language_2.pdf[^]
http://www.ime.usp.br/~pf/Kernighan-Ritchie/C-Programming-Ebook.pdf[^]
-----
The debugger is a nice tool to understand what a program is doing

When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. It allow you to execute lines 1 by 1 and to inspect variables as it execute, it is an incredible learning tool.

Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]

The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.
 
Share this answer
 
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS


CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900