10310 - Dog and Gopher

[JWizard]

I don't know why I keep getting wrong answer... works fine with all the data I tried....

[c]#include <stdio.h>
#include <math.h>

int main()
{
int n;
double gx, gy, dx, dy;
while(5 == scanf("%d %lf %lf %lf %lf", &n, &gx, &gy, &dx, &dy))
{
int i, j, s = 0;
for(i = 0 ; i < n ; i++)
{
double x, y, dg, dd;
scanf("%lf %lf", &x, &y);
dg = hypot(gx-x, gy-y);
dd = hypot(dx-x, dy-y);
if(dg*2.0 < dd)
{
printf("The gopher can escape through the hole at (%.3f,%.3f).\n", x, y);
s = 1;
break;
}
}
if(!s) printf("The gopher cannot escape.\n");
}
return 0;
} [/c]

While we are on the topic, does anyone have any tips for finding "tricky" input ?

Thanks

[Hauser]

I've used long longs, not doubles, and I've got AC.
(You can simply operate on numbers multiplied by 1000).
Also, you don't have to use sqrt function, or something. You can simply
compare squares of numbers.


Hauser

[seolv]

I tried to solve this problem too but I got WA.

I think,, the solution of this problem is obvious and the reason why i got WA is something related floating number arithmatics.

I changed double to long datatype but it doesn't work. --;

Do you know any good sites that explain floating number errors?

plz answer me

[Hauser]

I haven't check if 'long' is enough, but I've used instead 'long long'
(it is 64bit integer, 2x bigger than normal long which is 32bit), and I got AC.

Some parts of my program:

[c]
long long dog_x, dog_y;
long long gopher_x, gopher_y;

int can_escape( long long x, long long y)
{

long long dog_l, gopher_l;

dog_l = (x-dog_x)*(x-dog_x) + (y-dog_y)*(y-dog_y);
gopher_l = (x-gopher_x)*(x-gopher_x) + (y-gopher_y)*(y-gopher_y);

if( 4*gopher_l <= dog_l )
return 1;
else
return 0;

}
[/c]


When reading numbers from input, you should multiply them by 1000.
To read a number I've used this function:

[c]int get_spaces(void)
{
int c;
while( isspace(c=getchar()) );
ungetc( c, stdin );
return c;
}

long long get_number(void)
{
int c;
int minus=1;
int i;
long long result = 0;
c=get_spaces();


if( c=='-' ) {
minus = -1;
getchar();
}

while( (c=getchar())!=' ' && c!='.') {
result *= 10;
result += c-'0';
}

if( c==' ' )
return minus*result*1000;

for( i=0; i<3; i++ ) {
c=getchar();
if( c==' ' )
break;

result *= 10;
result += c-'0';
}

while( i<3 ) {
result *= 10;
i++;
}

return minus*result;
}[/c]

I think it can be done much easier, but thats the way i've done it.
You should also use some yours printing method.

Hauser

[Johnny_T]

Apparently if the gopher reaches the hole at the same time as the dog it is considered that he escapes...

[scythe]

This is easier:
[c]
scanf("%d.%d", &a, &b);
x = (long long) (a * 1000 + b);
[/c]

[scythe]

Sorry, that wouldnt work for negative numbers
Still, i got ac using double data type and an 1e-7 epsilon.

[SilVer DirectXer]

i have tested many cases and i cant see any errors..
[cpp]
#include <iostream.h>
#include <stdio.h>
#include <math.h>
class co{
public:
double x;
double y;
};
co dog, g,holes[1003];
int pts;
int i,j,k;
double dd,dg;
int a;
int gx,gy,hx,hy,dx,dy;
void main(void)
{
while (1)
{
cin>>pts;
if (cin.eof())
break;
cin>>g.x;
cin>>g.y;
gx=g.x*1000;
gy=g.y *1000;
cin>>dog.x;
cin>>dog.y;
dx=dog.x*1000;
dy=dog.y*1000;


for (i=0;i<pts;i++)
{
cin>>holes[i].x >>holes[i].y ;
}
for (i=0;i<pts;i++)
{
hx=holes[i].x *1000;
hy=holes[i].y *1000;

dd=(dx-hx)*(dx-hx)+(dy-hy)*(dy-hy) ;
dd=sqrt(dd);
dd/=2;

dg=(gx-hx)*(gx-hx )+(gy-hy )*(gy-hy );
dg=sqrt(dg);

a=0;
if (dd>dg)
{
a=1;
printf("The gopher can escape through the hole at (%.3f,%.3f).\n",holes[i].x ,holes[i].y );
break;
}

}
if (a==0)
cout<<"The gopher cannot escape."<<endl;
}


}
[/cpp]

[deddy one]

have you try

if (dd>=dg)


notice the '=' there.

[beska]

I think I'm having the same problem, though I'm using Java. I'm getting WA, even though the algorithm seems obvious. I am checking for >= rather than strictly >, so that's not the issue... Any bizzare test cases people have would help.[/java]

[deddy one]

when I first submit I use '>'
and get Wa, when I changed it
to '>=' then I get Ac

I use double to solve this using C

[FlareCDE]

A few things I noticed. You need to check for equals, as posted above. Doubles seem to help, my floats gave me WA. Another big thing is to watch for integer division in c++. dogDist/2 gives a WA, but dogDist/2.0 does not :). Be careful there, this one is simple but a few minor programming nuances can really mess it up.

[turuthok]

For problems like this, logically, it's straightforward to solve using floating-points operations (i.e.: using doubles). But, if you're skeptical about it because of precision stuff ... use integer operation. I think this problem is very doable using integer operation ... (e.g.: multiply the input numbers with 1000 ... or something like that).

My AC-ed solution is using double, though ...

-turuthok-

[stcheung]

People, perhaps this may be the most useful tip on getting your 10310 program to AC. First of all, you can use doubles (no need to use long long and multiply input by 1000 blahblah). Secondly, when the dog & gopher reach the hole at same time, it's still considered a successful escape. Lastly, and definitely NOT the least, if you are lazy like me and didn't take sqrt when calculating distances, then when you compare the dog & gopher distances, remember to multiply gopher distance by 4 (or divide dog distance by 4). Multiplying/dividing by 2 doesn't work if you HAVE NOT taken square root (and that's how I keep getting WA at first).

~Sunny

[bugzpodder]

I have:
1) made the output precision to 3 decimal places
2) output the first available hole and ignored all the ones after inputting them
3) if dog and gopher reaches a hole at the same time, gopher escapes
4) used long long to avoid any precision error (including not taking sqrt and using 4 to replace 2 upon squaring)

but i still cannot get the problem. please help!!

[cpp]

#include<iostream>
#include<cmath>
#include<iomanip>
//#include<fstream>
using namespace std;

long long dist(long long a, long long b){
return a*a+b*b;
}


int main(){
long long d1,d2,gx,gy,dx,dy,hx,hy;
int N,i;
double dgx,dgy,ddx,ddy,dhx,dhy;
bool flag;

while(cin>>N>>dgx>>dgy>>ddx>>ddy){
gx=(long long)(dgx*1000ULL); gy=(long long)(dgy*1000ULL);
dx=(long long)(ddx*1000ULL); dy=(long long)(ddy*1000ULL);
flag=false;
for (i=0;i<N;i++){
cin>>dhx>>dhy;
if (flag) continue;
hx=(long long)(dhx*1000ULL); hy=(long long)(dhy*1000ULL);
d1=dist(hx-dx,hy-dy);
d2=(4ULL)*dist(hx-gx,hy-gy);
if (d1>=d2){
flag=true;
cout<<"The gopher can escape through the hole at (";
cout<<setiosflags(ios::fixed)<<setprecision(3)<<dhx<<","<<dhy<<")."

<<endl;
}
}
if (!flag) cout<<"The gopher cannot escape."<<endl;
}
return 0;
}[/cpp]