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.
, Manzoor Bhai at his best 