## 10310 - Dog and Gopher

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

Moderator: Board moderators

JWizard
New poster
Posts: 5
Joined: Mon Jul 01, 2002 4:21 pm
Contact:

### 10310 - Dog and Gopher

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
New poster
Posts: 4
Joined: Tue Aug 13, 2002 7:32 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
seolv
New poster
Posts: 11
Joined: Wed Oct 24, 2001 2:00 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?

plz answer me
Hauser
New poster
Posts: 4
Joined: Tue Aug 13, 2002 7:32 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
Johnny_T
New poster
Posts: 2
Joined: Fri Sep 27, 2002 2:30 am

### Why the possible Wrong Answer

Apparently if the gopher reaches the hole at the same time as the dog it is considered that he escapes...
scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

### Re:

This is easier:
[c]
scanf("%d.%d", &a, &b);
x = (long long) (a * 1000 + b);
[/c]
scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

### Sorry

Sorry, that wouldnt work for negative numbers
Still, i got ac using double data type and an 1e-7 epsilon.
SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

### 10310...WA

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;
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]
deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm
have you try

if (dd>=dg)

notice the '=' there.
beska
New poster
Posts: 2
Joined: Thu Mar 13, 2003 2:10 am

### I dunno...

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
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 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
FlareCDE
New poster
Posts: 3
Joined: Fri Mar 21, 2003 6:31 pm
Location: New York
Contact:
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.
- Flare Araxion
turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
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-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

### math is always important...

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
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

### 10310 - Dog and Gopher

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]
Last edited by bugzpodder on Tue Sep 23, 2003 12:54 am, edited 1 time in total.