Page 6 of 7

Re: WHY WA? PLZ HELP

Posted: Mon May 14, 2012 5:29 pm
by Evan72

Code: Select all

removed

Re: 10245 - The Closest Pair Problem

Posted: Mon May 14, 2012 11:29 pm
by brianfry713
Input:

Code: Select all

2
0.3 1.2
0.7 5.2
0
AC output:

Code: Select all

4.0200

Re: 10245 - The Closest Pair Problem

Posted: Wed Jul 11, 2012 8:47 pm
by Evan72
Thanks brianfry713.. silly mistake :( :@

Re: 10245 - The Closest Pair Problem

Posted: Thu Oct 04, 2012 3:56 am
by liuhb86
I've tested all the testcase here, and still get WA. Where is the problem? Thanks

Code: Select all

The code has gone.

Re: 10245 - The Closest Pair Problem

Posted: Thu Oct 04, 2012 11:01 pm
by brianfry713
First I think you may have to clear your sortY and maybe your tmp and points arrays between each case.
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
AC output:255.1085

Re: 10245 - The Closest Pair Problem

Posted: Fri Oct 05, 2012 9:05 am
by liuhb86
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.
brianfry713 wrote:First I think you may have to clear your sortY and maybe your tmp and points arrays between each case.
Try input:

10245 - The Closest Pair Problem

Posted: Wed Feb 27, 2013 5:22 pm
by AirFishQi
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;
}

Re: 10245 - The Closest Pair Problem

Posted: Wed Feb 27, 2013 5:59 pm
by lbv
AirFishQi wrote:I still got a lot of WA... I Don't know why....
You may try debugging these cases:

Input

Code: Select all

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

Code: Select all

13.8924
INFINITY
By the way, there were already two threads for this problem. Please search the forums before posting your question, and use an existing thread if possible. Thanks.

Re: 10245 - The Closest Pair Problem

Posted: Thu Feb 28, 2013 4:23 pm
by AirFishQi
Thanks for your help.

Re: 10245 - The Closest Pair Problem

Posted: Wed May 29, 2013 2:36 pm
by army007
I think there is a mistake in the problem statement.
Out specification says -
If there is no such two points in the input whose distance is less than 10000, print the line INFINITY.
This means for a set of points if minimum distance is 10000.0000 output should be "INFINITY".
But my code that prints 10000.0000 in such a case got AC.

Re: 10245 - The Closest Pair Problem

Posted: Fri Sep 20, 2013 8:04 pm
by MPC1984
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! : :oops:
Here it's my Java code:

Code: Select all

AC code
Thanks in advance :wink:

Re: 10245 - The Closest Pair Problem

Posted: Fri Sep 20, 2013 10:49 pm
by brianfry713
You can use a stack instead of recursion.

Re: 10245 - The Closest Pair Problem

Posted: Thu Oct 03, 2013 9:59 pm
by MPC1984
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.
:roll:

Re: 10245 - The Closest Pair Problem

Posted: Fri Oct 04, 2013 3:00 am
by brianfry713

Re: 10245 - The Closest Pair Problem

Posted: Tue Oct 08, 2013 7:31 pm
by MPC1984
Thank you brianfry713! I got AC with your help. :wink: