10245 - The Closest Pair Problem

[isagooddaytodie]

how to compare all pairs faster than O(n^2) it gives TLE of course

My algo is here.
1) Sort data in ascending order based on x coordinates.
2) Set default minimum distance d(d is distance between point1 and point2.

3) Restrict the x-range with d.
4) Copy 1) between x-range of 3).
5) --Sort 4) in ascending order based on y coordinates.
6) --Restrict the y-range with d.
7) --Measure the distance -> new_d.
--Update d if new_d is smaller than d.
9) Back to 3).

This algorithm can be see in this site.
The point of this algorithm is to reduce the number of times of measuring the distance.

Best regards.

sorry but I will rewrite this so it's more clear.

this is called the sweep plane algorithm.

1) Sort the points according to x using a !!!!!!O(nlog(n))!!!!! algorithm.
So the relationship between the points can be identified. We call this sorted list of points S.

2) Divide the points into two groups according to their x-value using the x-vaule of the median of S. We call the two groups S1 and S2. Now using x-vaule of the median of S might not be best in some situations, but in this problem with unknown inputs, it's fine. (DO NOT physically divide them. How to do you do this then? Look at the index of the median you will see a hot blonde chick... or dude... *shivers*, whichever you prefer.)

3) Find the minimum distances between 2 points in each of the two groups by recursion using these steps. we will call them d1 and d2. The recursive method will back track when of course, there's only 3 points or less in the current S we are looking at. We return minimum distance within this no-more-than-3-vertices graph using brute force.

4) And d3 will be the minimum distance between any two points in S such that one point come from the first group and the other point come from the second group. This must be done using special methods or else you will still end up with a O(n^2) or worst if you use brute force. One of them is described below.

----------------------------------------------------------------------------------

Since we know d1 and d2, and we must find the minimum of the distances, we take the lesser of the two, let's call it d12(Hey! Who says rappers can't be good at math. m'^-^'m), as a search limit when we are looking for d3.

a) We extract all points with its x-value within -d12 of the x-value of the median of S. we call it S1x.

b) We extract all points with its x-value within d12 of the x-value of the median of S. We call it S2x.

c) Sort S1x and s2x using each points' y-value.

d) For each point in S1x we find the minimum distance to S2x such that the the points we look at in S2x have a y-value that is within d12 range of S1x point's y-value. We will end up with a set of minimum distance.

e) Now we set d3 equal to the minimum of that set. And returns.

meow you can just operate on one list instead of S1x and S2x, which save you some memory, but seperating the list will help you on bookkeeping by getting rid of some if statments.

------------------------------------------------------------------------------------

5) The minimum of d1, d2 and d3 will be your answer.

Any fall through cases will set the minimum distance returning to Max distance, which is given in the problem.


note: Think a little about how the algorithm works before you start coding will help you a lot. Maybe you'll find a better solution.

[Darko]

I generated some random cases and I get exactly the same answers with both brute force and my solution. I guess I have some precision issues or something.

I have no idea what to try next, I think I should only run into precision problems in the cases where you print "INFINITY". I tried >=10000, >10000, >=9999.9999999, I have no idea what else I can try.

Anyone has some cases for this?

[EDIT] I just realized there are no Java AC solutions. Is it the same problem as it was with 10215? (it is the same problem setter)

[EDIT2] I appologize to the problem setter, it was a silly mistake, in the case of 2 points I just printed the distance without checking if it was >=10000.

[WingletE]

I use sqrt() every time when I compare the distance and I got WA. But when I change and use sqrt() only once when printing the result, I got TLE.
It's so strange! Could anyone help?
Thanks.

[Mohamed Abd El-Monem]

I'm a beginer in c++, and I get TLE in this problem

PLZ any one tell me what make it TLE

this is my code

Code: Select all

# include <iostream>
# include <cmath>
# include  <iomanip>
using namespace std;

struct Dimension
{
	double X_coordinate;
	double Y_coordinate;
};


double DISTANCE[49995500]; 

int main()
{
	Dimension point[10000];

	int NumberOfPoints;
	while( cin>>NumberOfPoints )
	{
		if (NumberOfPoints == 0)
			break;

		int counter=0;

		for (int i=0;i<NumberOfPoints;i++)
		{
			cin >> point[i].X_coordinate;
			cin >> point[i].Y_coordinate;
		}

		double MIN=10000;

		for (int i=0;i<NumberOfPoints;i++)
		{

			for (int j=i;j<NumberOfPoints-1;j++)
			{
				double X=0,Y=0;

				X = point[i].X_coordinate - point[j+1].X_coordinate;
				Y = point[i].Y_coordinate - point[j+1].Y_coordinate;

				if ( X < 0 )
					X *= -1;
				if ( Y < 0 )
					Y *= -1;

				double distance;

				distance = pow(X,2) + pow(Y,2);

				DISTANCE[counter] = sqrt(distance);
				

				if (DISTANCE[counter] < MIN)
					MIN = DISTANCE[counter];

				counter++;


			}
		}

		
		if (MIN >= 10000)
		{
			cout<<"INFINITY"<<endl;
			continue;
		}

		cout<<setiosflags(ios::fixed)<<setprecision(4)<<MIN<<endl;




	}

	return 0;
}

thanx in advance

[Jan]

Try to implement the algorithm - 'Closest pair problem'. (Remember that google is your friend)

[bad_boy]

Hi there!
My code could run all other input posted.
But I'm not sure about this

2
0 10000
0 0.00001
2
0 10000
0 0.0001
2
0 10000
0 0.0009
2
0 10000
0 0.00009

what are the correct answers ?
Thank you!

[Jan]

I think there are no such cases. However, my accepted code generates...

Output:

Code: Select all

10000.0000
9999.9999
9999.9991
9999.9999

The actual result for the first case is almost 9999.999990. And the rounded result is 10000. However, my code fails to find it, and I am sure that there are no such cases. And of course this problem is not a serious 'rounding tricky' problem.

[Leonid]

I passed all of the test cases in this thread but still WA. I used the same algo with another task which I solved, but it's not working here. Probably it's a precision issue or something. Any ideas?

Code: Select all

#include <time.h>
#include <algorithm> 
#include <iostream>  
#include <sstream> 
#include <string> 
#include <vector> 
#include <queue> 
#include <stack>
#include <set> 
#include <map> 
#include <cstdio> 
#include <cstdlib> 
#include <cctype> 
#include <cmath> 
#include <cassert>
using namespace std;

#define PB push_back
#define MP make_pair
#define SZ(v) ((int)(v).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n) FORE(i,0,n)
#define FORSZ(i,a,v) FOR(i,a,SZ(v))
#define REPSZ(i,v) REP(i,SZ(v))
#define FILL(a,b) memset(a, (b), sizeof(a));
typedef long long ll; 
const double EPS = 1e-7;

void openfiles() {
	#ifndef ONLINE_JUDGE
		freopen("test.in","rt",stdin);
		//freopen("test.out","wt",stdout);   
	#endif
}

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

bool eq(double a, double b) {
	return a < b + EPS && a > b - EPS;
}

bool byx(const Point& a, const Point& b) {
	if (!eq(a.x,b.x)) return a.x < b.x;
	return a.y < b.y; // this is a crucial part!
}

bool byy(const Point& a, const Point& b) {
	return a.y < b.y;
}



double divide(vector<Point>& P, vector<Point>& X, vector<Point>& Y) {
	int n = SZ(P);
	if (n <= 3) {
		double best = 1000000000;
		REP(i,n) REP(j,n) if (i != j) best = min(best, hypot(P[i].x - P[j].x, P[i].y - P[j].y));
		return best;
	}

	// divide into 2 parts
	double m = X[n / 2].x;
	double my = X[n / 2].y;

	vector<Point> LX(X.begin(), X.begin() + n / 2);
	vector<Point> RX(X.begin() + n / 2, X.end());
	vector<Point> LP(P.begin(), P.begin() + n / 2);
	vector<Point> RP(P.begin() + n / 2, P.end());
	vector<Point> LY, RY;

	REP(i,n) if (Y[i].x + EPS < m || (eq(Y[i].x,m) && Y[i].y + EPS < my) ) LY.push_back(Y[i]); else RY.push_back(Y[i]);
	assert(SZ(LY) == SZ(LX));

	double r = divide(RP, RX, RY);
	double l = divide(LP, LX, LY);
	
	double b = min(r, l);

	// create the middle part with points
	vector<Point> R;
	REP(i,n) if (Y[i].x > m - b && Y[i].x < m + b) R.push_back(Y[i]);
	int rn = SZ(R);
	double q = 1000000000;
	REP(i,rn) for (int j = 1; j <= 10 && i + j < rn; j++) {
		q = min(q, hypot(Y[i].x - Y[i + j].x, Y[i].y - Y[i + j].y) );
	}

	return min(q, b);
}

bool solve() {
	int n;
	if (scanf("%d",&n) != 1 || n == 0) return false;
	vector<Point> P(n);
	REP(i,n) scanf("%lf %lf",&P[i].x,&P[i].y);
	REP(i,n) P[i].k = i;

	vector<Point> X = P, Y = P;
	sort(X.begin(), X.end(), byx);
	sort(Y.begin(), Y.end(), byy);

	REP(i,n-1) if (eq(X[i].x,X[i+1].x) && eq(X[i].y,X[i+1].y)) {
		printf("0.0000\n");
		return true;
	}

	double r = divide(P, X, Y);
	if (r + EPS > 10000) {
		printf("INFINITY\n");
	}
	else {
		printf("%.4lf\n", r + 1e-10);
	}

	return true;
}

int main() {
	openfiles();
	while (solve());

	return 0;
}

[Leonid]

Any ideas will still be appreciated...

[stcheung]

Some previous threads actually made this problem seem harder than it is. So let me make it sound simpler.

This is a standard solution that uses the divide-and-conquer strategy, just like mergesort.
(1) First sort the points by x-coordinate.
(2) Divide the points into 2 halves, just like you would for mergesort.
(3) Determine the minimum distance between the points within each half recursively.
(4) Compare the minimum distance from each half, and let "d" be the smaller value.
(5) We are not done yet, because the distance between a point on left half and a point on right half may actually be smaller than "d". Let p be the midpoint with which you divided the set of points into 2 halves in step (2). Let S1 be the set of points in left half, whose x-coordinate is within "d" of point p. Define S2 analogously for the right half. For each point in S1, compute the distance with each point in S2, and note whether any of these distances is smaller than "d".
(6) "d" is now the answer we are looking for

Note that sqrt() is expensive and so you should only use it at the end, and NOT when comparing distances in the steps above.
Also note that you need to carry out step (5) above for each recursive call. This should be intuitive. My step 5 above is actually a simplification of what the real standard algorithm would do, but the extra time it takes isn't a big deal and my Java solution can still get AC for <0.6 sec.

[Obaida]

Why m wa!!!!
my method is simple and i think fast too. But why this gives wa!!!
some one plz help me..

Code: Select all

removed

[newkid]

@Obaida
the problem statement says "N (0<=N<=10000)"
from your code..

Code: Select all

int n,x[1001],y[1001],i,j;

You should have got RE instead of WA (I donno why). I dont think O(N^2) will pass the timelimit. There is standard algorithm for finding closest pair in cartesian plane.

[Obaida]

Hi,
i increased my array size bt... could u look at this..

6933397 10245 The Closest Pair Problem Wrong answer C++ 0.000 2009-02-07 06:09:59

This is my code...

Code: Select all

removed

[newkid]

hmm.. got the problem.. the problem statement says "The next N line contains the coordinates of N two-dimensional points. The first of the two numbers denotes the X-coordinate and the latter denotes the Y-coordinate". It never said the coordinates are Integer. if you change your array type to double, you will get TLE as expected.

[Obaida]

Thank you.. i will try with good algo..