Closest Pair of Points

help
1

Problem Statement - Given n points in a 2D plane. Find the closest euclidean distance possible.
I have understood the underlying principle that has to be used to solve the problem but my code is not working. More specifically the output I am getting is the min value I declare in my bruteForce Function.
Please help me debug the code.

#include <bits/stdc++.h>
using namespace std;

class point
{
public:
int x,y;
};

double min(double a,double b)
{
if (a<b) return a;
else return b;
}

double dist(point a,point b)
{
double ans = sqrt((a.x-b.x)(a.x-b.x)+(a.y-b.y)(a.y-b.y));
return ans;
}

// 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);
}

// A Brute Force method to return the smallest distance between two points
// in P[] of size n
double bruteForce(point P[], int l,int r)
{
double mini = 1e9;
for (int i = l; i < r; ++i)
for (int j = i+1; j <= r; ++j)
if (dist(P[i], P[j]) < mini)
mini = dist(P[i], P[j]);
return mini;
}

double strip(int midpt,point sorted_py[],double mini,int n)
{
point arr[n];
int size=0;
for (int i=0;i<n;i++)
if (abs(sorted_py[i].x-midpt)<mini)
arr[size++]=sorted_py[i];

for (int i=0;i<size-1;i++)
    for (int j=i+1;(j<size && (arr[j].y-arr[i].y)<mini);j++)
        if (dist(arr[i],arr[j])<mini) 
            mini=dist(arr[i],arr[j]);
            
return mini;

}

double divide(point sorted_px[],point sorted_py[],int l,int r,int n)
{
if (r-l<=3) return bruteForce(sorted_px,l,r);
double ans=0;
int mid=(l+r)/2;
int midpt=sorted_px[mid].x;
ans=min(divide(sorted_px,sorted_py,0,mid,n),
divide(sorted_px,sorted_py,mid+1,r,n));

ans=min(ans,strip(midpt,sorted_py,ans,n));
return ans;

}

int main() {
int n;
point p[n];
for (int i=0;i<n;i++)
cin >> p[i].x >> p[i].y;

point sorted_px[n],sorted_py[n];
for (int i=0;i<n;i++)
{
    sorted_px[i]=p[i];
    sorted_py[i]=p[i];
}
qsort(sorted_px,n,sizeof(point),compareX);
qsort(sorted_py,n,sizeof(point),compareY);

cout << divide(sorted_px,sorted_py,0,n-1,n) << endl;
return 0;

}

2

Firstly, you’ve got to post the link to the problem, for making sure that it is not from an ongoing contest. Also, please consider formatting the text as its hurting my eyes and you don’t want to hurt anyone’s eyes, do you?

1 Like
3

@vijju123 - would it be possible to add a few simple Guidelines that show up when Create New Topic is chosen? Things like “Please format code” and “If this is a question, please link to the source” etc?

3 Likes
4

Also, here’s an obvious resource from an unembellished Google search.

5

I think maybe not. Its a much wanted request from me as well and was suggested sometime back as well. Let me recheck it again. :slight_smile:

2 Likes
6

Ok - not sounding promising, but I’m crossing all my fingers :slight_smile:

2 Likes
7

this is a very basic textbook problem and cannot be given in a contest…I will surely consider formatting