10245 - The Closest Pair Problem

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

isagooddaytodie
New poster
Posts: 3
Joined: Tue Mar 13, 2007 11:04 am
Contact:

Post by isagooddaytodie » Tue May 01, 2007 12:24 am

tan_Yui wrote:
jaracz wrote: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.
8) --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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Jul 17, 2007 1:04 am

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.

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Post by WingletE » Fri Aug 17, 2007 5:37 am

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
New poster
Posts: 15
Joined: Mon Mar 31, 2008 1:20 am
Location: Egypt
Contact:

Re: 10245 Trick input?

Post by Mohamed Abd El-Monem » Tue Apr 01, 2008 11:07 pm

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
Last edited by Mohamed Abd El-Monem on Tue Apr 01, 2008 11:52 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10245 Trick input?

Post by Jan » Tue Apr 01, 2008 11:14 pm

Try to implement the algorithm - 'Closest pair problem'. (Remember that google is your friend)
Ami ekhono shopno dekhi...
HomePage

bad_boy
New poster
Posts: 2
Joined: Thu Apr 03, 2008 5:00 pm

Re: 10245 - The Closest Pair Problem

Post by bad_boy » Sat Apr 19, 2008 3:56 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10245 - The Closest Pair Problem

Post by Jan » Sun Apr 20, 2008 5:38 pm

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.
Ami ekhono shopno dekhi...
HomePage

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 10245 - The Closest Pair Problem

Post by Leonid » Mon Aug 25, 2008 10:25 pm

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
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 10245 - The Closest Pair Problem

Post by Leonid » Thu Sep 25, 2008 10:01 pm

Any ideas will still be appreciated...

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10245 - The Closest Pair Problem

Post by stcheung » Sat Oct 18, 2008 5:41 am

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
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10245 - The Closest Pair Problem

Post by Obaida » Thu Feb 05, 2009 7:16 am

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

Code: Select all

removed
Last edited by Obaida on Sat Feb 07, 2009 8:09 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

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

Re: 10245 - The Closest Pair Problem

Post by newkid » Fri Feb 06, 2009 3:17 am

@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.
hmm..

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10245 - The Closest Pair Problem

Post by Obaida » Sat Feb 07, 2009 8:13 am

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
Last edited by Obaida on Sat Feb 07, 2009 8:47 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

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

Re: 10245 - The Closest Pair Problem

Post by newkid » Sat Feb 07, 2009 8:44 am

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.
hmm..

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10245 - The Closest Pair Problem

Post by Obaida » Sat Feb 07, 2009 8:45 am

Thank you.. i will try with good algo.. :)
try_try_try_try_&&&_try@try.com
This may be the address of success.

Post Reply

Return to “Volume 102 (10200-10299)”