10245 - The Closest Pair Problem

[newkid]

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");

[Obaida]

Thank you...

[amine.hamdaoui]

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]

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
instead of

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

instead of

Code: Select all

float

whenever possible..

[batiestuta]

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]

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]

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
      readln(a[i,1],a[i,2]);
  end;
begin
  
  readln(n);
  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);
      readln(n);
    end;
 
end.

[plamplam]

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.

[AhmadKhatar]

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!
Thanks in advance!

[brianfry713]

Doesn't match the sample I/O.

[AhmadKhatar]

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

[brianfry713]

Input

Code: Select all

2
0 0
7071.0678118654752440084436210485 7071.0678118654752440084436210485
0

AC output:
10000.0000

[AhmadKhatar]

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]

You misspelled INFINITY.

[AhmadKhatar]

Thank you for the time that you spent on finding my error!
Finally I received AC.