Page 1 of 4

### 10310 - Dog and Gopher

Posted: Sun Aug 04, 2002 1:02 am
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

Posted: Tue Aug 13, 2002 7:41 pm
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

Posted: Sat Aug 17, 2002 9:35 am
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?

Posted: Sat Aug 17, 2002 7:54 pm
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

### Why the possible Wrong Answer

Posted: Fri Sep 27, 2002 2:32 am
Apparently if the gopher reaches the hole at the same time as the dog it is considered that he escapes...

### Re:

Posted: Tue Oct 08, 2002 5:07 pm
This is easier:
[c]
scanf("%d.%d", &a, &b);
x = (long long) (a * 1000 + b);
[/c]

### Sorry

Posted: Wed Oct 09, 2002 5:06 pm
Sorry, that wouldnt work for negative numbers
Still, i got ac using double data type and an 1e-7 epsilon.

### 10310...WA

Posted: Sun Apr 13, 2003 6:34 am
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.x >>holes.y ;
}
for (i=0;i<pts;i++)
{
hx=holes.x *1000;
hy=holes.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.x ,holes.y );
break;
}

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

}
[/cpp]

Posted: Sun Apr 20, 2003 6:18 pm
have you try

if (dd>=dg)

notice the '=' there.

### I dunno...

Posted: Tue Apr 22, 2003 9:41 pm
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]

Posted: Wed Apr 23, 2003 4:28 pm
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

Posted: Wed Apr 23, 2003 10:36 pm
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.

Posted: Wed Apr 23, 2003 11:19 pm
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-

### math is always important...

Posted: Mon May 19, 2003 11:28 am
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

### 10310 - Dog and Gopher

Posted: Sat Sep 20, 2003 4:06 am
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)

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