10245 - The Closest Pair Problem

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Evan72
New poster
Posts: 11
Joined: Sat Apr 28, 2012 2:01 pm

Re: WHY WA? PLZ HELP

Post by Evan72 » Mon May 14, 2012 5:29 pm

Code: Select all

removed
Last edited by Evan72 on Wed Jul 11, 2012 8:47 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10245 - The Closest Pair Problem

Post by brianfry713 » Mon May 14, 2012 11:29 pm

Input:

Code: Select all

2
0.3 1.2
0.7 5.2
0
AC output:

Code: Select all

4.0200
Check input and AC output for thousands of problems on uDebug!

Evan72
New poster
Posts: 11
Joined: Sat Apr 28, 2012 2:01 pm

Re: 10245 - The Closest Pair Problem

Post by Evan72 » Wed Jul 11, 2012 8:47 pm

Thanks brianfry713.. silly mistake :( :@

liuhb86
New poster
Posts: 3
Joined: Wed Oct 03, 2012 5:26 pm

Re: 10245 - The Closest Pair Problem

Post by liuhb86 » 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.
Last edited by liuhb86 on Fri Oct 05, 2012 9:07 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10245 - The Closest Pair Problem

Post by brianfry713 » 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:

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
Check input and AC output for thousands of problems on uDebug!

liuhb86
New poster
Posts: 3
Joined: Wed Oct 03, 2012 5:26 pm

Re: 10245 - The Closest Pair Problem

Post by liuhb86 » 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.
brianfry713 wrote:First I think you may have to clear your sortY and maybe your tmp and points arrays between each case.
Try input:

AirFishQi
New poster
Posts: 2
Joined: Wed Feb 27, 2013 4:25 pm

10245 - The Closest Pair Problem

Post by AirFishQi » 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;
}

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10245 - The Closest Pair Problem

Post by lbv » Wed Feb 27, 2013 5:59 pm

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.

AirFishQi
New poster
Posts: 2
Joined: Wed Feb 27, 2013 4:25 pm

Re: 10245 - The Closest Pair Problem

Post by AirFishQi » Thu Feb 28, 2013 4:23 pm

Thanks for your help.

army007
New poster
Posts: 6
Joined: Tue Feb 19, 2013 10:34 pm
Location: Dhaka, Bangladesh

Re: 10245 - The Closest Pair Problem

Post by army007 » Wed May 29, 2013 2:36 pm

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.
Human knowledge belongs to the world.

MPC1984
New poster
Posts: 40
Joined: Mon Jul 01, 2013 9:24 pm
Location: Valladolid, Spain

Re: 10245 - The Closest Pair Problem

Post by MPC1984 » 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! : :oops:
Here it's my Java code:

Code: Select all

AC code
Thanks in advance :wink:
Last edited by MPC1984 on Tue Oct 08, 2013 7:29 pm, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10245 - The Closest Pair Problem

Post by brianfry713 » Fri Sep 20, 2013 10:49 pm

You can use a stack instead of recursion.
Check input and AC output for thousands of problems on uDebug!

MPC1984
New poster
Posts: 40
Joined: Mon Jul 01, 2013 9:24 pm
Location: Valladolid, Spain

Re: 10245 - The Closest Pair Problem

Post by MPC1984 » 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.
:roll:
Last edited by MPC1984 on Tue Oct 08, 2013 7:30 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10245 - The Closest Pair Problem

Post by brianfry713 » Fri Oct 04, 2013 3:00 am

Check input and AC output for thousands of problems on uDebug!

MPC1984
New poster
Posts: 40
Joined: Mon Jul 01, 2013 9:24 pm
Location: Valladolid, Spain

Re: 10245 - The Closest Pair Problem

Post by MPC1984 » Tue Oct 08, 2013 7:31 pm

Thank you brianfry713! I got AC with your help. :wink:

Post Reply

Return to “Volume 102 (10200-10299)”