10245 - The Closest Pair Problem

[Evan72]

Code: Select all

removed

[brianfry713]

Input:

Code: Select all

2
0.3 1.2
0.7 5.2
0

AC output:

Code: Select all

4.0200

[Evan72]

Thanks brianfry713.. silly mistake :@

[liuhb86]

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

Code: Select all

The code has gone.

[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

[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.

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

[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;
}

[lbv]

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.

[AirFishQi]

Thanks for your help.

[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.

[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! :
Here it's my Java code:

Code: Select all

AC code

Thanks in advance

[brianfry713]

You can use a stack instead of recursion.

[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.

[brianfry713]

http://en.wikipedia.org/wiki/Recursion_ ... _iteration

[MPC1984]

Thank you brianfry713! I got AC with your help.