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.