### Re: WHY WA? PLZ HELP

Posted:

**Mon May 14, 2012 5:29 pm**Code: Select all

`removed`

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=17&t=72304

Page **6** of **7**

Posted: **Mon May 14, 2012 11:29 pm**

Input:
AC output:

Code: Select all

```
2
0.3 1.2
0.7 5.2
0
```

Code: Select all

`4.0200`

Posted: **Wed Jul 11, 2012 8:47 pm**

Thanks brianfry713.. silly mistake :@

Posted: **Thu Oct 04, 2012 3:56 am**

I've tested all the testcase here, and still get WA. Where is the problem? Thanks

Code: Select all

```
The code has gone.
```

Posted: **Thu Oct 04, 2012 11:01 pm**

First I think you may have to clear your sortY and maybe your tmp and points arrays between each case.

Try input:AC output:255.1085

Try input:

Code: Select all

```
90
17392.8 23045.1
24003.2 8249.9
16480.3 31007.4
1728.9 11285.0
11508.3 13965.7
6445.3 8105.0
32962.1 30779.4
5987.1 26761.2
39025.9 10545.0
18942.0 26502.6
8893.0 10155.4
21354.4 12309.0
36084.4 34687.9
27194.0 20945.2
34490.3 25278.9
8324.0 31622.9
39872.8 11883.1
2890.5 32327.2
15247.5 16353.1
1954.0 16254.7
24359.7 26755.8
29170.4 20034.6
18431.0 17321.8
27866.9 6792.8
4930.6 17456.9
27612.3 6808.9
30753.1 13823.6
20146.8 8966.7
29911.9 38472.7
35386.8 7340.8
10598.9 36037.4
7920.6 3710.8
7673.3 10471.7
38460.1 22446.3
38701.0 22920.8
21311.8 12049.3
3719.1 23060.7
12017.8 10482.2
17275.0 22150.1
39607.0 11519.9
29964.0 22205.7
7664.5 27219.3
7821.2 32352.3
30825.0 27811.3
6787.3 9368.4
5405.8 37847.1
13193.1 17386.2
39493.2 13326.4
35772.8 20866.4
15422.4 9588.5
21637.8 34473.8
29169.8 36734.2
18851.7 25357.0
19142.3 12822.8
24342.7 36126.7
29967.6 18749.4
17603.9 14306.7
18294.2 9267.4
37078.7 25425.2
34793.6 9119.2
18601.5 15501.3
32887.5 199.4
25161.1 31794.7
12661.1 32380.7
13604.4 20933.9
27042.9 39718.8
8088.2 6877.5
3869.7 27847.9
12305.9 26939.9
34701.9 23012.0
1761.4 36648.6
22590.5 36304.7
5572.1 19365.4
16425.8 884.7
21639.2 14286.1
29787.4 11219.4
23054.0 240.7
3670.6 34310.1
38326.1 8215.1
784.2 27967.0
27685.8 11930.5
18808.0 39462.4
27310.3 35774.0
34349.2 34312.9
17325.0 39616.3
7900.1 29051.1
25355.8 19086.4
10087.0 2125.9
3010.6 2563.2
28484.5 26512.8
0
```

Posted: **Fri Oct 05, 2012 9:05 am**

It's not the reinitialization problem, but a silly mistake in the n=2 boundary case(yes, related to sortY)...

Thanks a lot brianfry!

BTW, uva works today without clearing the cookies.

Thanks a lot brianfry!

BTW, uva works today without clearing the cookies.

brianfry713 wrote:First I think you may have to clear your sortY and maybe your tmp and points arrays between each case.

Try input:

Posted: **Wed Feb 27, 2013 5:22 pm**

I still got a lot of WA... I Don't know why....

Code: Select all

```
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define MAX_NUM 10010
using namespace std;
struct POINT {
double x, y;
} point[ MAX_NUM ];
double distance( struct POINT *a, struct POINT *b )
{
double x = (*a).x - (*b).x;
double y = (*a).y - (*b).y;
return (double)sqrt( x * x + y * y );
}
bool cmp( struct POINT a, struct POINT b )
{
return a.x < b.x;
}
double find_min( int L, int R )
{
if ( R - L <= 3 ) /* Less than 3 points */
{
double d = distance( &point[L], &point[R-1] );
for ( int i = 0; i < R - L - 1; i++ )
d = min ( distance( &point[L], &point[L+1] ), d );
return d;
}
int mid = ( L + R ) / 2, l = 0, r = 0;
double d = min( find_min( L, mid ), find_min( mid, R ) );
for ( l = mid - 1; l >= 0; l-- )
if ( ( point[mid].x - point[l].x ) - 1e-9 > d ) break;
if ( l < 0 ) l = 0;
for ( r = mid + 1; r < R; r++ )
if ( ( point[r].x - point[mid].x ) - 1e-9 > d ) break;
for ( int i = l; i < mid + 1; i++ )
for ( int j = mid; j < r; j++ )
{
if ( i != j )
d = min( distance( &point[i], &point[j] ), d );
}
return d;
}
int main ()
{
int n = 0;
while ( scanf("%d", &n) && n )
{
for ( int i = 0; i < n; i++ )
scanf( "%lf %lf", &(point[i].x), &(point[i].y) );
sort( point, point + n, cmp ); /* sort by x */
double result = find_min( 0, n );
if ( result > 10000.0f && fabs( result - 10000.0f ) > 1e-10 )
cout << "INFINITY" << endl;
else printf( "%.4lf\n", result);
}
return 0;
}
```

Posted: **Wed Feb 27, 2013 5:59 pm**

You may try debugging these cases:AirFishQi wrote:I still got a lot of WA... I Don't know why....

Code: Select all

```
6
10 17
28 77
83 82
95 89
67 81
22 52
1
42 42
0
```

Code: Select all

```
13.8924
INFINITY
```

Posted: **Thu Feb 28, 2013 4:23 pm**

Thanks for your help.

Posted: **Wed May 29, 2013 2:36 pm**

I think there is a mistake in the problem statement.

Out specification says -*10000.0000* output should be *"INFINITY"*.

But my code that prints 10000.0000 in such a case got AC.

Out specification says -

This means for a set of points if minimum distance isIf there is no such two points in the input whose distance is less than 10000, print the line INFINITY.

But my code that prints 10000.0000 in such a case got AC.

Posted: **Fri Sep 20, 2013 8:04 pm**

Hi everybody!

I' ve tried divide and conquer algorithm for this problem, but I have serious problems with recursive algorithms, how can I do to avoid recursive calls and use a loop?. Please help me! :

Here it's my Java code:
Thanks in advance

I' ve tried divide and conquer algorithm for this problem, but I have serious problems with recursive algorithms, how can I do to avoid recursive calls and use a loop?. Please help me! :

Here it's my Java code:

Code: Select all

```
AC code
```

Posted: **Fri Sep 20, 2013 10:49 pm**

You can use a stack instead of recursion.

Posted: **Thu Oct 03, 2013 9:59 pm**

Hi brianfry713! Thank you for your answer, but I don't undestand you when you say I can use stacks instead of recursion.

What should I put in the stacks? The ordered points, the distances between the points?

I have tried brute force algorithm TLE, I have tried divide and conquer algorithm TLE (in Java, because the same code in C++ AC), and I want to solve it in Java.

What should I put in the stacks? The ordered points, the distances between the points?

I have tried brute force algorithm TLE, I have tried divide and conquer algorithm TLE (in Java, because the same code in C++ AC), and I want to solve it in Java.

Posted: **Fri Oct 04, 2013 3:00 am**

Posted: **Tue Oct 08, 2013 7:31 pm**

Thank you brianfry713! I got AC with your help.