## 10245 - The Closest Pair Problem

Moderator: Board moderators

### Re: 10245 - The Closest Pair Problem

And for future reference
Code: Select all
`if(fabs(min-10001)<0.00001)  puts("INFINITY");`

this logic is wrong. you will print INFINITY only when min == 10001 and all other cases where min > 10000 it wont print INFINITY. use the following
Code: Select all
`if(min > 10000.0 || fabs(min-10000.0)<0.00001)  puts("INFINITY");`
hmm..
newkid
Learning poster

Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 10245 - The Closest Pair Problem

Thank you...
try_try_try_try_&&&_try@try.com
This may be the address of success.
Obaida
A great helper

Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 10245 - The Closest Pair Problem

Can some one tell me what is wrong in this code, i use Brute Force, but it gives me WA?
Code: Select all
`#include <stdio.h>#include <math.h>int main(){    int i,j,N;    float X[10000],Y[10000],dist,d;    do    {        scanf("%d",&N);        if(N==0)        break;        dist = 10001;        for(i=0 ; i<N ; i++)        {            scanf("%f%f",&X[i],&Y[i]);            for(j=0 ; j<i ; j++)            {                d = ((X[i]-X[j])*(X[i]-X[j]))+(Y[i]-Y[j])*(Y[i]-Y[j]);                if(dist>d)                {                    dist = d;                }            }        }        if(dist<=10000) printf("%.4f\n",sqrt(dist));        else printf("INFINITY\n");    } while(1);    return 0;}`
amine.hamdaoui
New poster

Posts: 10
Joined: Tue Aug 07, 2007 7:33 pm

### Re: 10245 - The Closest Pair Problem

amine.hamdaoui wrote:
Code: Select all
` ....                d = ((X[i]-X[j])*(X[i]-X[j]))+(Y[i]-Y[j])*(Y[i]-Y[j]);....        if(dist<=10000) printf("%.4f\n",sqrt(dist));        else printf("INFINITY\n");`

So dist basically holds the squared distance. in your if condition shouldn't you be doing
Code: Select all
` dist = sqrt(dist);if (dist <= 10000) printf("%.4f\n", dist);else printf("INFINITY\n");`

Anyway as mentioned earlier in this thread, a brute force algo will not pass the time limit.
and a small hint on comparing equality on floating point number
Code: Select all
`if (dist <= 10000) `
do
Code: Select all
`if (dist < 10000 || fabs(dist - 10000) < 1e-7)`

and try to use
Code: Select all
`double`
Code: Select all
`float`
whenever possible..
hmm..
newkid
Learning poster

Posts: 73
Joined: Fri Dec 12, 2008 3:06 am

### Re: 10245 - The Closest Pair Problem

I've tried all the sample inputs,and get the correct answers.
But I stiil WA for many times.

I'am very upset.

Please give me some help! Thanks at first.

Code: Select all
`program u10245;var  ans:double;  n,i:longint;  a:array[0..10000,1..2]of double;function dis(o1,o2:longint):double;  var    t:double;  begin    t:=sqrt(sqr(a[o1,1]-a[o2,1])+sqr(a[o1,2]-a[o2,2]));    exit(t);  end;function min(o1,o2:double):double;  begin    if o1<o2      then exit(o1)      else exit(o2);  end;procedure qs(l,r:longint;ip:integer);  var    m:double;    i,j:longint;    t:array[1..2]of double;  begin    i:=l;j:=r;m:=a[(i+j)shr 1,ip];    repeat      while a[i,ip]<m do inc(i);      while m<a[j,ip] do dec(j);      if i<=j        then begin               t:=a[i];               a[i]:=a[j];               a[j]:=t;               inc(i);               dec(j);             end;    until i>j;    if i<r then qs(i,r,ip);    if l<j then qs(l,j,ip);  end;function ef(l,r:longint):double;  var    mid,m,i,j,k,o,x,ll,rr:longint;    e:double;  begin    if l=r      then exit(10001);    mid:=(l+r)shr 1;    e:=min(ef(mid+1,r),ef(l,mid));    i:=mid;j:=mid;    qs(l,r,1);    while (a[i,1]>a[mid,1]-e)and(i>l) do dec(i);    while (a[j,1]<a[mid,1]+e)and(j<r) do inc(j);    qs(i,mid,2);    qs(mid+1,j,2);    if mid<j      then    for k:=i to mid do      begin        ll:=mid+1;rr:=j;x:=ll;        while ll<rr do          if a[rr,2]<a[k,2]            then begin                   x:=rr;                   break;                 end            else if a[ll,2]>=a[k,2]                   then begin                          x:=ll;                          break;                        end                   else begin                          m:=(ll+rr)shr 1;                          if a[m,2]<=a[k,2]                            then rr:=m                            else ll:=m;                          x:=rr;                        end;        for o:=x downto x-3 do          if o<mid+1            then break            else e:=min(e,dis(k,o));        for o:=x+1 to x+4 do          if o>j            then break            else e:=min(e,dis(k,o));      end;    exit(e);  end;procedure int(n:longint);  var    i:longint;  begin    for i:=1 to n do      readln(a[i,1],a[i,2]);  end;begin    readln(n);  while n<>0 do    begin      int(n);      qs(1,n,1);      ans:=ef(1,n);      if ans>=9999.99995        then writeln('INFINITY')        else writeln(ans:0:4);      readln(n);    end; end.`
Kevin Tso
New poster

Posts: 1
Joined: Thu Aug 19, 2010 6:37 am

### Re: 10245 - The Closest Pair Problem

With certainty that it will get Time Limit, I submitted my O(n^2) program to the judge and guess what? I got Accepted in less than 1 second!! Now I read in the board that everyone is saying O(n^2) can't pass the time limit, etc etc. So, I just wanted to inform future viewers that a O(n^2) algorithm gets Accepted now.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

plamplam
Experienced poster

Posts: 151
Joined: Fri May 06, 2011 11:37 am

### Re: WHY WA? PLZ HELP

Code: Select all
`removed`
Last edited by Evan72 on Wed Jul 11, 2012 8:47 pm, edited 1 time in total.
Evan72
New poster

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

### Re: 10245 - The Closest Pair Problem

Input:
Code: Select all
`20.3 1.20.7 5.20`

AC output:
Code: Select all
`4.0200`
brianfry713
Guru

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

### Re: 10245 - The Closest Pair Problem

Thanks brianfry713.. silly mistake :@
Evan72
New poster

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

### Re: 10245 - The Closest Pair Problem

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.
liuhb86
New poster

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

### Re: 10245 - The Closest Pair Problem

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
`9017392.8 23045.124003.2 8249.916480.3 31007.41728.9 11285.011508.3 13965.76445.3 8105.032962.1 30779.45987.1 26761.239025.9 10545.018942.0 26502.68893.0 10155.421354.4 12309.036084.4 34687.927194.0 20945.234490.3 25278.98324.0 31622.939872.8 11883.12890.5 32327.215247.5 16353.11954.0 16254.724359.7 26755.829170.4 20034.618431.0 17321.827866.9 6792.84930.6 17456.927612.3 6808.930753.1 13823.620146.8 8966.729911.9 38472.735386.8 7340.810598.9 36037.47920.6 3710.87673.3 10471.738460.1 22446.338701.0 22920.821311.8 12049.33719.1 23060.712017.8 10482.217275.0 22150.139607.0 11519.929964.0 22205.77664.5 27219.37821.2 32352.330825.0 27811.36787.3 9368.45405.8 37847.113193.1 17386.239493.2 13326.435772.8 20866.415422.4 9588.521637.8 34473.829169.8 36734.218851.7 25357.019142.3 12822.824342.7 36126.729967.6 18749.417603.9 14306.718294.2 9267.437078.7 25425.234793.6 9119.218601.5 15501.332887.5 199.425161.1 31794.712661.1 32380.713604.4 20933.927042.9 39718.88088.2 6877.53869.7 27847.912305.9 26939.934701.9 23012.01761.4 36648.622590.5 36304.75572.1 19365.416425.8 884.721639.2 14286.129787.4 11219.423054.0 240.73670.6 34310.138326.1 8215.1784.2 27967.027685.8 11930.518808.0 39462.427310.3 35774.034349.2 34312.917325.0 39616.37900.1 29051.125355.8 19086.410087.0 2125.93010.6 2563.228484.5 26512.80`
AC output:255.1085
brianfry713
Guru

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

### Re: 10245 - The Closest Pair Problem

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:
liuhb86
New poster

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

### Re: 10245 - The Closest Pair Problem

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.
army007
New poster

Posts: 3
Joined: Tue Feb 19, 2013 10:34 pm