## 10245 - The Closest Pair Problem

Moderator: Board moderators

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 10245 - The Closest Pair Problem

And for future reference

Code: Select all

``````if(fabs(min-10001)<0.00001)
puts("INFINITY");``````
this logic is wrong. you will print INFINITY only when min == 10001 and all other cases where min > 10000 it wont print INFINITY. use the following

Code: Select all

``````if(min > 10000.0 || fabs(min-10000.0)<0.00001)
puts("INFINITY");``````
hmm..

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 10245 - The Closest Pair Problem

Thank you...
try_try_try_try_&&&_try@try.com
This may be the address of success.

amine.hamdaoui
New poster
Posts: 10
Joined: Tue Aug 07, 2007 7:33 pm

### Re: 10245 - The Closest Pair Problem

Can some one tell me what is wrong in this code, i use Brute Force, but it gives me WA?

Code: Select all

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

int main()
{
int i,j,N;
float X[10000],Y[10000],dist,d;

do
{
scanf("%d",&N);
if(N==0)        break;
dist = 10001;
for(i=0 ; i<N ; i++)
{
scanf("%f%f",&X[i],&Y[i]);
for(j=0 ; j<i ; j++)
{
d = ((X[i]-X[j])*(X[i]-X[j]))+(Y[i]-Y[j])*(Y[i]-Y[j]);
if(dist>d)
{
dist = d;
}
}
}

if(dist<=10000) printf("%.4f\n",sqrt(dist));
else printf("INFINITY\n");
} while(1);

return 0;
}
``````

newkid
Learning poster
Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 10245 - The Closest Pair Problem

amine.hamdaoui wrote:

Code: Select all

`````` ....
d = ((X[i]-X[j])*(X[i]-X[j]))+(Y[i]-Y[j])*(Y[i]-Y[j]);
....
if(dist<=10000) printf("%.4f\n",sqrt(dist));
else printf("INFINITY\n");
``````
So dist basically holds the squared distance. in your if condition shouldn't you be doing

Code: Select all

`````` dist = sqrt(dist);
if (dist <= 10000) printf("%.4f\n", dist);
else printf("INFINITY\n");
``````
Anyway as mentioned earlier in this thread, a brute force algo will not pass the time limit.
and a small hint on comparing equality on floating point number

Code: Select all

``if (dist <= 10000) ``
do

Code: Select all

``if (dist < 10000 || fabs(dist - 10000) < 1e-7)``
and try to use

Code: Select all

``double``

Code: Select all

``float``
whenever possible..
hmm..

batiestuta
New poster
Posts: 1
Joined: Fri Oct 16, 2009 2:29 pm

### 10245 Closest Pair

I keep getting WA, can not find bugs in my code. Can anyone helps me out. Thanks

Code: Select all

``````#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int sz = 10009;
const double inf = 1e20;

typedef struct node{
double x, y;
}node;

node a[sz], x[sz];
int t[sz], n;

struct cmpx{
bool operator()(const node& lhs, const node& rhs)
{
return lhs.x < rhs.x;
}
};

struct cmpy{
bool operator()(const node& lhs, const node& rhs)
{
return lhs.y < rhs.y;
}
};

double closest_pair(int l, int r)
{
int j, k, p, m;
double dx, dy;
double ans, delta;
if(r - l <= 2){
for(j = l, ans = inf; j <= r - 1; j++){
for(k = j + 1; k <= r; k++){
dx = a[j].x - a[k].x;
dy = a[j].y - a[k].y;
if(dx * dx + dy * dy < ans){
ans = dx * dx + dy * dy;
}
}
}
return ans;
}
else{
m = l + (r - l)/2;
ans = min(closest_pair(l, m), closest_pair(m + 1, r));
delta = sqrt(ans);
for(j = l, k = 0; j <= r; j++){
if( (x[m].x - a[j].x)  <= delta){
t[k++] = j;
}
}
for(j = 0; j < k; j++){
for(p = j + 1; p < k && (a[t[p]].y - a[t[j]].y) <= delta; p++){
dx = a[t[j]].x - a[t[p]].x;
dy = a[t[j]].y - a[t[p]].y;
if(dx * dx + dy * dy < ans){
ans = dx * dx + dy * dy;
}
}
}
return ans;
}
}

int main()
{
int j;
double ans;
while(scanf("%d", &n) && n){
for(j = 0; j < n; j++){
scanf("%lf%lf", &a[j].x, &a[j].y);
x[j] = a[j];
}
if(n == 1){
printf("INFINITY\n");
}
else{
sort(a, a + n, cmpy());
sort(x, x + n, cmpx());
ans = closest_pair(0, n - 1);
ans = sqrt(ans);
if(ans - 10000 >= 1e-10){
printf("INFINITY\n");
}
else{
printf("%.4f\n", ans);
}
}
}
return 0;
}
``````

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 10245 Closest Pair

I got a lot of Wa,while compare a square distance, when I change to normal distance(sqrt) I got Ac!
And change this:
if(ans - 10000 >= 1e-10) to
if(ans <10000.0 && fabs(ans-10000.0)<1e-10)

Kevin Tso
New poster
Posts: 1
Joined: Thu Aug 19, 2010 6:37 am

### Re: 10245 - The Closest Pair Problem

I've tried all the sample inputs,and get the correct answers.
But I stiil WA for many times.

I'am very upset.

Please give me some help! Thanks at first.

Code: Select all

``````program u10245;
var
ans:double;
n,i:longint;
a:array[0..10000,1..2]of double;
function dis(o1,o2:longint):double;
var
t:double;
begin
t:=sqrt(sqr(a[o1,1]-a[o2,1])+sqr(a[o1,2]-a[o2,2]));
exit(t);
end;
function min(o1,o2:double):double;
begin
if o1<o2
then exit(o1)
else exit(o2);
end;
procedure qs(l,r:longint;ip:integer);
var
m:double;
i,j:longint;
t:array[1..2]of double;
begin
i:=l;j:=r;m:=a[(i+j)shr 1,ip];
repeat
while a[i,ip]<m do inc(i);
while m<a[j,ip] do dec(j);
if i<=j
then begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if i<r then qs(i,r,ip);
if l<j then qs(l,j,ip);
end;
function ef(l,r:longint):double;
var
mid,m,i,j,k,o,x,ll,rr:longint;
e:double;
begin
if l=r
then exit(10001);
mid:=(l+r)shr 1;
e:=min(ef(mid+1,r),ef(l,mid));
i:=mid;j:=mid;
qs(l,r,1);
while (a[i,1]>a[mid,1]-e)and(i>l) do dec(i);
while (a[j,1]<a[mid,1]+e)and(j<r) do inc(j);
qs(i,mid,2);
qs(mid+1,j,2);
if mid<j
then
for k:=i to mid do
begin
ll:=mid+1;rr:=j;x:=ll;
while ll<rr do
if a[rr,2]<a[k,2]
then begin
x:=rr;
break;
end
else if a[ll,2]>=a[k,2]
then begin
x:=ll;
break;
end
else begin
m:=(ll+rr)shr 1;
if a[m,2]<=a[k,2]
then rr:=m
else ll:=m;
x:=rr;
end;
for o:=x downto x-3 do
if o<mid+1
then break
else e:=min(e,dis(k,o));
for o:=x+1 to x+4 do
if o>j
then break
else e:=min(e,dis(k,o));
end;
exit(e);
end;
procedure int(n:longint);
var
i:longint;
begin
for i:=1 to n do
end;
begin

while n<>0 do
begin
int(n);
qs(1,n,1);
ans:=ef(1,n);
if ans>=9999.99995
then writeln('INFINITY')
else writeln(ans:0:4);
end;

end.

``````

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 10245 - The Closest Pair Problem

With certainty that it will get Time Limit, I submitted my O(n^2) program to the judge and guess what? I got Accepted in less than 1 second!! Now I read in the board that everyone is saying O(n^2) can't pass the time limit, etc etc. So, I just wanted to inform future viewers that a O(n^2) algorithm gets Accepted now.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

### Re: 10245 Closest Pair

Hi!
Here is my code for the problem:

Code: Select all

``````#define INFINITY 10000

#include <iostream>
using std::cin;
using std::cout;
using std::endl;
using std::fixed;

#include <iomanip>
using std::setprecision;

#include <algorithm>
using std::sort;

#include <cmath>
using std::sqrt;
using std::fabs;

using std::min;

struct Point
{
int index;
double x, y;
};

Point xP [ 10000 ];
Point yP [ 10000 ];
double xMess [ 10000 ];
double yMess [ 10000 ];

bool isLeft [ 10000 ];
Point yStrip [ 10000 ];
int n;

void process();
bool cmpFnX( Point p1, Point p2 );
bool cmpFnY( Point p1, Point p2 );
double cpp( int stInd, int endInd, int yInds [] );
double distance( Point p1, Point p2 );

int main()
{
cin >> n;
while ( n != 0 )
{
double tX, tY;
for ( int i = 0; i < n; i++ )
{
cin >> tX >> tY;
xP[ i ].index = yP[ i ].index = i;
xMess[ i ] = xP[ i ].x = yP[ i ].x = tX;
yMess[ i ] = xP[ i ].y = yP[ i ].y = tY;
}
process();
cin >> n;
}

return 0;
}

void process()
{
sort( &xP[ 0 ], &xP[ n ], cmpFnX );
sort( &yP[ 0 ], &yP[ n ], cmpFnY );

int firstYInds [ 10000 ];
for ( int i = 0; i < n; i++ )
{
firstYInds[ i ] = yP[ i ].index;
}

double result = cpp( 0, n - 1, firstYInds );
if ( result >= INFINITY )
{
cout << "INFINTIY" << endl;
}
else
{
cout << fixed << setprecision( 4 ) << result << endl;
}
}

double cpp( int stInd, int endInd, int yInds [] ) // stInd and endInd are on xP
{
int pNo = endInd - stInd + 1;
int yIndsL [ 5000 ];
int yIndsR [ 5000 ];

if ( pNo == 1 )
{
return INFINITY;
}
else if ( pNo == 2 )
{
return distance( xP[ 0 ], xP[ 1 ] );
}
else if ( pNo >= 3 ) // number of points is more than or equal to 3
{
int mid = ( stInd + endInd ) / 2;

for ( int i = stInd; i <= mid; i++ )
{
isLeft[ xP[ i ].index ] = true;
}

for ( int i = mid + 1; i <= endInd; i++ )
{
isLeft[ xP[ i ].index ] = false;
}

int k1 = 0;
int k2 = 0;
for ( int i = 0; i < pNo; i++ )
{
if ( isLeft[ yInds[ i ] ] == true )
{
yIndsL[ k1++ ] = yInds[ i ];
}
else
{
yIndsR[ k2++ ] = yInds[ i ];
}
}

double distL, distR;

if ( stInd <= mid )
{
distL = cpp( stInd, mid, yIndsL );
}
else
{
distL = INFINITY;
}

if ( mid + 1 <= endInd )
{
distR = cpp( mid + 1, endInd, yIndsR );
}
else
{
distR = INFINITY;
}

double lrDist = min( distL, distR );
Point midPoint = xP[ mid ];

// Construct yStrip array, in increasing y order
int strCnt = 0;
for ( int i = 0; i < pNo; i++ )
{
if ( fabs( xMess[ yInds[ i ] ] - midPoint.x ) < lrDist )
{
yStrip[ strCnt ].x = xMess[ yInds[ i ] ];
yStrip[ strCnt ].y = yMess[ yInds[ i ] ];
// no need to initialize yStrip[strCnt].index
strCnt++;
}
}
// yStrip constructed

double minDist = lrDist;
for ( int i = 0; i < strCnt - 1; i++ )
{
double tDist;
for ( int j = i + 1; j < strCnt && yStrip[ j ].y - yStrip[ i ].y < lrDist; j++ ) // why lrDist, why not minDist?!
{
tDist = distance( yStrip[ j ], yStrip[ i ] );
minDist = min( tDist, minDist );
}
}

return minDist;
}
}

double distance( Point p1, Point p2 )
{
return sqrt( ( p1.x - p2.x ) * ( p1.x - p2.x ) +
( p1.y - p2.y ) * ( p1.y - p2.y ) + 0.0 );
}

bool cmpFnX( Point p1, Point p2 )
{
return p1.x < p2.x;
}

bool cmpFnY( Point p1, Point p2 )
{
return p1.y < p2.y;
}
``````
My code passed many test cases. I generated many random inputs and all of them returned correct output. But I receive WA. Please help me to find the mistake!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10245 Closest Pair

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

### Re: 10245 Closest Pair

Hi!
First of all thank you for your great help brianfry!
In Visual C++ there was no errors but when I compiled the code in Dev-C++ output was wrong. Because of the constant name INFINITY. I changed it to INFIN and the error disappeared but I still get WA.
Here is my code:

Code: Select all

``````#define INFIN 10000

#include <iostream>
using std::cin;
using std::cout;
using std::endl;
using std::fixed;

#include <iomanip>
using std::setprecision;

#include <algorithm>
using std::sort;

#include <cmath>
using std::sqrt;
using std::fabs;

using std::min;

struct Point
{
int index;
double x, y;
};

Point xP [ 10000 ];
Point yP [ 10000 ];
double xMess [ 10000 ];
double yMess [ 10000 ];

bool isLeft [ 10000 ];
Point yStrip [ 10000 ];
int n;

void process();
bool cmpFnX( Point p1, Point p2 );
bool cmpFnY( Point p1, Point p2 );
double cpp( int stInd, int endInd, int yInds [] );
double distance( Point p1, Point p2 );

int main()
{
cin >> n;
while ( n != 0 )
{
double tX, tY;
for ( int i = 0; i < n; i++ )
{
cin >> tX >> tY;
xP[ i ].index = yP[ i ].index = i;
xMess[ i ] = xP[ i ].x = yP[ i ].x = tX;
yMess[ i ] = xP[ i ].y = yP[ i ].y = tY;
}
process();
cin >> n;
}

return 0;
}

void process()
{
sort( &xP[ 0 ], &xP[ n ], cmpFnX );
sort( &yP[ 0 ], &yP[ n ], cmpFnY );

int firstYInds [ 10000 ];
for ( int i = 0; i < n; i++ )
{
firstYInds[ i ] = yP[ i ].index;
}

double result = cpp( 0, n - 1, firstYInds );
if ( result >= INFIN )
{
cout << "INFINTIY" << endl;
}
else
{
cout << fixed << setprecision( 4 ) << result << endl;
}
}

double cpp( int stInd, int endInd, int yInds [] ) // stInd and endInd are on xP
{
int pNo = endInd - stInd + 1;
int yIndsL [ 5000 ];
int yIndsR [ 5000 ];

if ( pNo == 1 )
{
return INFIN;
}
else if ( pNo == 2 )
{
return distance( xP[ stInd ], xP[ endInd ] );
}
else if ( pNo >= 3 ) // number of points is more than or equal to 3
{
int mid = ( stInd + endInd ) / 2;

for ( int i = stInd; i <= mid; i++ )
{
isLeft[ xP[ i ].index ] = true;
}

for ( int i = mid + 1; i <= endInd; i++ )
{
isLeft[ xP[ i ].index ] = false;
}

int k1 = 0;
int k2 = 0;
for ( int i = 0; i < pNo; i++ )
{
if ( isLeft[ yInds[ i ] ] == true )
{
yIndsL[ k1++ ] = yInds[ i ];
}
else
{
yIndsR[ k2++ ] = yInds[ i ];
}
}

double distL, distR;

if ( stInd <= mid )
{
distL = cpp( stInd, mid, yIndsL );
}
else
{
distL = INFIN;
}

if ( mid + 1 <= endInd )
{
distR = cpp( mid + 1, endInd, yIndsR );
}
else
{
distR = INFIN;
}//cout << distL << " " << distR << endl;

double lrDist = min( distL, distR );
Point midPoint = xP[ mid ];

// Construct yStrip array, in increasing y order
int strCnt = 0;
for ( int i = 0; i < pNo; i++ )
{
if ( fabs( xMess[ yInds[ i ] ] - midPoint.x ) < lrDist )
{
yStrip[ strCnt ].x = xMess[ yInds[ i ] ];
yStrip[ strCnt ].y = yMess[ yInds[ i ] ];
// no need to initialize yStrip[strCnt].index
strCnt++;
}
}
// yStrip constructed

double minDist = lrDist;
for ( int i = 0; i < strCnt - 1; i++ )
{
double tDist;
for ( int j = i + 1; j < strCnt && yStrip[ j ].y - yStrip[ i ].y < lrDist; j++ ) // why lrDist, why not minDist?!
{
tDist = distance( yStrip[ j ], yStrip[ i ] );
minDist = min( tDist, minDist );
}
}

return minDist;
}
}

double distance( Point p1, Point p2 )
{
return sqrt( ( p1.x - p2.x ) * ( p1.x - p2.x ) +
( p1.y - p2.y ) * ( p1.y - p2.y ) + 0.0 );
}

bool cmpFnX( Point p1, Point p2 )
{
return p1.x < p2.x;
}

bool cmpFnY( Point p1, Point p2 )
{
return p1.y < p2.y;
}
``````
Last edited by AhmadKhatar on Thu Apr 05, 2012 12:40 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10245 Closest Pair

Input

Code: Select all

``````2
0 0
7071.0678118654752440084436210485 7071.0678118654752440084436210485
0``````
AC output:
10000.0000
Check input and AC output for thousands of problems on uDebug!

New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

### Re: 10245 Closest Pair

Thanks so much!
I checked your input in http://www.uvatoolkit.com/problemssolve.php#10245 but the output was INFINITY. The problem says that if the distance is greater than or equal to 10000 the output should be INFINITY. There was a small error in my code in the base case of the recursive function but after it was corrected again I received WA. And I can not find the bug at all.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10245 Closest Pair

You misspelled INFINITY.
Check input and AC output for thousands of problems on uDebug!