## 10245 - The Closest Pair Problem

Moderator: Board moderators

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
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.

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
Thanks! I think I'm now in a good way to solve this in efficient time
standby
keep it real!

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
I did it like it was written in this site;
Only sort(qsort) and finding 2 minimal distances between points in 2 equal-size sets gives TLE
so I think it isn't such an efficient algo, must exist better

Could you explain much clear, or some example?
would be grateful
keep it real!

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Let's think about the following case (second Sample Input).
5
0 2
6 67
43 71
39 107
189 140
At first, sort data. --- (1)
Then, data will be the following.
0 2
6 67
39 107
43 71
189 140
Default value d = dist(&pt[0], &pt[1])
= sqrt((2 - 67)^2 + (0 - 6)^2)
= 65.276336 .--- (2)
The 'pt' is the array of coordinate data.

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

3) to 9) is the following calculation.

Code: Select all

/* restrict the x-range with d */
for(i=2; i<N; i++) {
for(j=i-1; j>=0; j--) {
if(pt[j].x + d < pt[i].x) break;
}
d = x_search(j+1, i, d);
}
First, check the x-range based on pt[2].x (= 39).
pt[2].x - pt[1].x = 39 - 6 = 33 < d(=65.276336) ,
pt[2].x - pt[0].x = 39 - 0 = 39 < d ,
so, the x-range is pt[0] to pt[2].

Code: Select all

double x_search(int L, int R, double d) {
int i, j;
double new_d;
memcpy(&part[0], &pt[L], (R-L+1)*sizeof(struct point));

/* sort in ascending order based on y coordinates */
qsort(part, R-L+1, sizeof(struct point), cmp_y);

/* restrict the y-range with d */
for(i=1; i<R-L+1; i++) {
for(j=i-1; j>=0; j--) {
if(part[j].y + d < part[i].y) break;
}
new_d = y_search(j+1, i, d);
if(new_d < d) d = new_d;
}
return d;
}
Copy data (pt[0] to pt[2]) to another array. --- (4)

Sort above array in ascending order based on y coordinates. --- (5)

Restrict the y-range with d. --- (6)
And function 'y_search' measures the distance by using my function 'dist'. --- (7)
(6) is like (3) calculation.

Code: Select all

double y_search(int Floor, int Ceil, double d) {
int i, j;
double new_d;
for(i=Floor; i<Ceil; i++) {
for(j=i+1; j<=Ceil; j++) {
new_d = dist(&part[i], &part[j]);
if(new_d < d) d = new_d;
}
}
return d;
}

Code: Select all

double dist(const void *e1, const void *e2) {
struct point a, b;

a = *((const struct point *)e1);
b = *((const struct point *)e2);

return sqrt((a.y - b.y)*(a.y - b.y) + (a.x - b.x)*(a.x - b.x));
}
new_d = y_search(0, 1, 65.276336) = 65.276336 ,
new_d = y_search(1, 2, 65.276336) = 51.855569 .

51.855569 < d, so update d (= 51.855569). --- (8)

Back to (3). --- (9)

------------------------------------------------------------
pt[3].x - pt[2].x = 4 < d(= 51.855569) ,
pt[3].x - pt[1].x = 37 < d ,
pt[3].x - pt[0].x = 43 < d ,
so, the x-range is pt[0] to pt[3] .

new_d = y_search(1, 1, 51.855569) = 51.855569 (in fact 0),
new_d = y_search(1, 2, 51.855569) = 37.215588 .
37.215588 < d, so update d (=37.215588).
new_d = y_search(2, 3, 37.215588) = 36.221541 .
36.221541 < d, so update d (=36.221541).

Back to (3).
------------------------------------------------------------
pt[4].x - pt[3].x = 146 > d(= 36.221541) ,
so, skip.
------------------------------------------------------------
break the loop (3).

Finally, d(= 36.221541) < 10000, so output 36.2215 .

Measure the distance of all pairs is too heavy to caluculate in time limit.
This algorithm restricts candidates of pairs.
If N is large, this method works efficiently.
jaracz wrote:I did it like it was written in this site;
Only sort(qsort) and finding 2 minimal distances between points in 2 equal-size sets gives TLE
so I think it isn't such an efficient algo, must exist better
If you get TLE using this method, your sorting part should be improved.
I used function 'qsort()'.

Because my explanation and English is poor,
I can send my code to your PM(Private Message) instead of explanation, if you want.

Best regards.

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
I said that I used qsort() (implemented in <stdlib.h> library),but finally got TLE, so let's turn to your algo now . I did similar (x_range) loop but gave me WA (was a bit different when i see now yours), I think I'll try to cope it by myself, basing on your advise, but if a fail(which is much possible) i'll turn to you again:)
Thanks
keep it real!

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
At last I've passed all in/out in efficient time indeed:)
OJ gave me CE but on my Dev-Cpp it runs,I'm supposed to fix it for a while i think i'm close to be ACed
Gr8 thx to you!! tan_Yui
keep it real!

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:
For those who are concerned I have used an assert as follows

Code: Select all

scanf("%lf %lf", &x, &y);

assert( (x-floor(x)) < eps );  //eps = small value = 1e-10
assert( (y-floor(y)) < eps );
The assert failes.. so I believe we can quite safely say that there is double in the input .. that is what have been gettin me WA .. the sample input is completely misleading.

But you can also not say that the problem description is wrong or illegal , Manzoor Bhai at his best

Some times even brute force gets WA
Where's the "Any" key?

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
My code passed all of the board testcases, but I got WA, can anybody help me?
This is my code:

Code: Select all

Spolier cutted off!
I got it!
Last edited by Moha on Wed May 24, 2006 11:07 am, edited 1 time in total.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Hi Moha!

I don't know what may be your problem, for my algo is 4 times as long
but look at this:

Code: Select all

double ans=floor(10000.*(sqrt(mind))+0.5)/10000.0;
if(ans>=10000.0)
printf("INFINITY\n");
else
printf("%.4lf\n",ans);
Well, we are accustomed to precision errors, but
I think this problem need not rounding at all.
Fragment of my AC code:

Code: Select all

delta=F(0,n-1);
if(delta<oo)
printf("%.4lf\n",delta);
else
printf("INFINITY\n");
Good luck!
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
for this input
• 2
0 10000
0 0.00001
2
0 10000
0 0.0001
2
0 10000
0 0.0009
2
0 10000
0 0.00009
• INFINITY
9999.9999
9999.9991
9999.9999
Am I correct?
Last edited by Moha on Wed May 24, 2006 11:12 am, edited 1 time in total.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
I got it at last. It was a precision error, because i wanted to compare the distance without using sqrt. now i changed my code to compute the exact distance with sqrt and i got it.
thanks to serur[\b] for his comment!

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Congratulations Moha!

10245 - very good question!
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am

### 10245 - Another WA

What might be the problem? I'm getting WA. My program ran from 1.758 seconds. Here is the sample inputs and outputs i tried:

Input:

Code: Select all

3
0 0
10000 10000
20000 20000
5
0 2
6 67
43 71
39 107
189 140
1
0 0
3
1 1
1 1
1 1
30
5253 2675
1436 1023
8447 1510
4610 406
538 4362
6299 2192
585 3791
5674 8538
9614 6466
6246 2506
915 4726
4660 411
5722 624
8857 6201
5093 7510
2588 2060
4949 4693
9181 5893
5443 7492
8136 329
4655 4812
9319 8815
4572 1012
3707 6556
1656 3150
520 4729
7037 8659
5251 1017
8617 1775
5644 573
30
647 806
998 945
395 611
641 923
423 625
490 684
327 571
767 821
792 294
963 157
366 960
208 350
142 205
767 467
850 596
251 331
888 270
376 359
153 466
87 930
106 321
702 85
644 860
161 895
228 999
163 471
410 580
43 770
394 800
199 819
30
184 125
253 37
364 470
155 331
233 341
18 322
337 207
237 357
249 51
146 470
308 441
24 227
155 367
375 475
319 119
283 113
329 298
428 258
134 387
58 82
273 263
260 256
177 112
242 410
112 297
318 496
433 204
28 376
341 81
204 217
30
134 154
151 212
48 129
204 61
203 130
58 226
191 41
68 225
234 90
135 146
30 135
177 14
148 24
65 33
150 86
56 52
226 69
215 74
243 178
184 73
60 10
65 113
6 55
20 168
175 212
222 104
16 39
79 201
187 126
133 80
100
283 211
947 1581
1915 1178
571 1753
1392 1459
1138 554
1399 1440
1000 1960
1686 1702
1383 229
1724 524
716 569
617 337
1429 1934
812 768
1119 1643
288 341
253 1456
694 29
1704 1286
97 1503
409 1076
1683 940
327 1185
283 1255
49 285
684 693
682 1869
380 1251
471 538
401 1802
1754 57
1339 772
1181 553
1297 1691
797 655
557 1109
1388 721
1543 641
132 52
578 1553
1964 1125
312 1045
1628 554
391 811
129 694
8 1465
80 1023
1939 38
905 256
133 1227
1331 652
764 1133
1617 873
1160 1527
1624 185
1090 1578
224 567
841 1364
1531 422
1505 1169
1785 762
490 612
183 322
1857 804
907 1884
25 375
241 86
1208 559
786 1013
833 1094
1929 1225
1604 139
1462 1899
1687 410
286 1292
1379 1837
1129 876
1887 613
1769 1756
893 326
1738 389
679 149
1919 1781
407 1427
119 1325
1272 1046
401 1131
1168 940
148 808
842 1151
1245 529
1397 919
1687 1270
815 1042
301 677
1343 452
1023 1428
677 1775
677 880
0
Output:

Code: Select all

INFINITY
36.2215
INFINITY
0.0000
50.2494
11.1803
12.0830
8.0623
20.2485
Can anyone give me any other tricky input and output? or any suggestions?

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:
Hi,

Maybe you forgot about floating-point input values?

Cu, Erik

Donotalo
Learning poster
Posts: 56
Joined: Sat Aug 20, 2005 11:05 am
No. I'm taking the inputs in double. Here is the pseudocode:

Code: Select all

struct Point {
double x, y;
};

int main()
{
int n, i, j;
double d;
Point point[10000];

while(cin >> n) {
if (n == 0) break;

for (i = 0; i < n; i++)
cin >> point[i].x >> point[i].y;

sort by x;
sort by y only the points those x coordinates are same;

d = min_distance(point, 0, n-1);
if (d >= 10000 || n == 1) printf("INFINITY\n");
else printf("%.4f\n", d);
}

return 0;
}
Any other thoughts?