# Closest Pair of Points

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.

#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;
``````

}

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

@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

Also, hereâ€™s an obvious resource from an unembellished Google search.

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.

2 Likes

Ok - not sounding promising, but Iâ€™m crossing all my fingers

2 Likes

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