10310  Dog and Gopher
Moderator: Board moderators
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(gxx, gyy);
dd = hypot(dxx, dyy);
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
[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(gxx, gyy);
dd = hypot(dxx, dyy);
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
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
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
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 = (xdog_x)*(xdog_x) + (ydog_y)*(ydog_y);
gopher_l = (xgopher_x)*(xgopher_x) + (ygopher_y)*(ygopher_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
(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 = (xdog_x)*(xdog_x) + (ydog_y)*(ydog_y);
gopher_l = (xgopher_x)*(xgopher_x) + (ygopher_y)*(ygopher_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
Apparently if the gopher reaches the hole at the same time as the dog it is considered that he escapes...

 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[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=(dxhx)*(dxhx)+(dyhy)*(dyhy) ;
dd=sqrt(dd);
dd/=2;
dg=(gxhx)*(gxhx )+(gyhy )*(gyhy );
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]
[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=(dxhx)*(dxhx)+(dyhy)*(dyhy) ;
dd=sqrt(dd);
dd/=2;
dg=(gxhx)*(gxhx )+(gyhy )*(gyhy );
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]
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]
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

 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 floatingpoints 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 ACed solution is using double, though ...
turuthok
My ACed solution is using double, though ...
turuthok
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).
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
~Sunny

 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(hxdx,hydy);
d2=(4ULL)*dist(hxgx,hygy);
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]
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(hxdx,hydy);
d2=(4ULL)*dist(hxgx,hygy);
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.