## 10310 - Dog and Gopher

Moderator: Board moderators

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 10310: vague problem statement

shadow wrote:The problem hasnt precisely defined the answer when the dog and the gopher both reach a hole at the same time. I think the answer in this case is "can reach".
you're right..

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil
so... if both reaches a role at same time, the dog eats the gopher...
that's right???

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
beloni wrote:so... if both reaches a role at same time, the dog eats the gopher...
that's right???
that case.. the gopher is safe..

isagooddaytodie
New poster
Posts: 3
Joined: Tue Mar 13, 2007 11:04 am
Contact:

### Re: math is always important...

stcheung wrote: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
And don't forget them outputs, oh boy do that thing blows up if you don't make it a 3 decimal pecision exact.

Itachi-Forsaken
New poster
Posts: 10
Joined: Mon May 07, 2007 4:45 am
Hi I'm trying to do this problem since the algorithm is straight forward but I can't AC for some reason so I was wondering if someone could kindly help me find the bugs in code =)

Here it is..hope someone can tell me what's wrong with it

Code: Select all

``````#include<iostream>
#include<stdio.h>
using namespace std;

typedef struct
{
double x, y;
}point;

inline double sqr(double n) { return n*n; }

int main()
{
while( !cin.eof() )
{
point dog, gopher;
int nholes, i, flag=0;
point hole, escape;
cin>>nholes;
cin>>gopher.x>>gopher.y>>dog.x>>dog.y;
for( i=0; i<nholes; i++ )
{
cin>>hole.x>>hole.y;
if( flag==1 ) continue;

if( (sqr(hole.x-dog.x)+sqr(hole.y-dog.y))>=4.0*(sqr(hole.x-gopher.x)+sqr(hole.y-gopher.y)) )
{
escape.x=hole.x; escape.y=hole.y;
flag=1;
}
}
if( flag==0 )
printf("The gopher cannot escape.\n");
else
printf("The gopher can escape through the hole at (%.3lf,%.3lf).\n", escape.x, escape.y);
}
return 0;
}
``````

yangmie
New poster
Posts: 3
Joined: Fri Nov 30, 2007 12:14 pm
Contact:
#include<stdio.h>
#include<math.h>
int main()
{
int n,k,temp;
double x1,y1,x2,y2;
double holeX,holeY;
double d1,d2;
while(scanf("%d%lf%lf%lf%lf",&n,&x1,&y1,&x2,&y2)==5)
{
temp=0;
for(k=0;k<n;k++)
{
scanf("%lf%lf",&holeX[k],&holeY[k]);
d1=sqrt((holeX[k]-x1)*(holeX[k]-x1)+(holeY[k]-y1)*(holeY[k]-y1));
d2=sqrt((holeX[k]-x2)*(holeX[k]-x2)+(holeY[k]-y2)*(holeY[k]-y2));
if(2*d1<=d2)
{
printf("The gopher can escape through the hole at (%.3lf,%.3lf).\n",holeX[k],holeY[k]);
temp=1;
break;
}
}
if(temp==0)printf("The gopher cannot escape.\n") ;
}
return 0;
}

why i got wa......?

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Try this:

Code: Select all

``````3 2.000 2.000 1.000 1.000
2.500 2.500
1.500 1.500
0.000 0.000
``````
-----
Rio

cyclops_kun
New poster
Posts: 4
Joined: Mon Dec 08, 2008 11:03 am

### I got AC in UVa judge, but i got WA in Programming-challenge

I got AC in UVa judge, but why i got WA in http://www.programming-challenges.com judge? I don't understand..
I'm sorry posting my AC code here , but, for me it's still WA , coz it's WA in programming-challenges, please help..thanks in advance.. Here is my code, for anyone who got AC, please try at http://www.programming-challenges.com and please tell me why i got WA there?

Code: Select all

``````#include<iostream>
#include<iomanip>
#include<cmath>
#define eps 1e-7

using namespace std;

double panjang(double x1, double y1, double x2, double y2);

int main()
{
int n;
double G1, G2, D1, D2;
double H;
int i, check;

cout<<fixed<<showpoint<<setprecision(3);
while(cin>>n>>G1>>G2>>D1>>D2)
{
check=0;
for(i=0; i<n; i++)
cin>>H[i]>>H[i];
for(i=0; i<n; i++)
{
if(panjang(D1,D2,H[i],H[i])>2*panjang(G1,G2,H[i],H[i]))
{
cout<<"The gopher can escape through the hole at ("<<H[i]+eps<<","<<H[i]+eps<<")."<<endl;
check++;
break;
}
}
if(check==0)
cout<<"The gopher cannot escape."<<endl;
}
return 0;
}
double panjang(double x1, double y1, double x2, double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
``````

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### 10310 - Dog and Gopher

whats wrong with my code??

Code: Select all

``````              #include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define eps 1e-7

double h;

int main()

{

int nhole,i,flag;

double x1,x2,y1,y2,dis_gof,dis_dog,h_x,h_y;

// freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);

while(scanf("%d",&nhole)==1)

{

//sscanf(str,"%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
scanf("%lf %lf %lf %lf\n",&x1,&y1,&x2,&y2);

for(i=0;i<nhole;i++)

{

scanf("%lf %lf",&h_x,&h_y);

//h_x=atof(str1);
//h_y=atof(str2);

dis_gof=(((x1-h_x)*(x1-h_x))+((y1-h_y)*(y1-h_y)));
printf("%lf\n",dis_gof);
dis_dog=((x2-h_x)*(x2-h_x))+((y2-h_y)*(y2-h_y));

printf("%lf\n",dis_dog);

if(dis_dog-4*dis_gof>=eps)

{

flag=1;
break;

}
else

{

flag=0;

}
scanf("\n");

}

//printf("flag=%d\n",flag);

if(flag==1)
printf("The gopher can escape through the hole at (%.3lf,%.3lf).\n",h_x,h_y);

else
printf("The gopher cannot escape.\n");

}
return 0;

}

``````
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

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

### Re: 10310 - Dog and Gopher

you are breaking the "for(i=0;i<nhole;i++)" loop if you find a suitable hole for the gopher. this loop happens to do the scanning as well "scanf("%lf %lf",&h_x,&h_y);". now tell me what will happen if you find a suitable hole before scanning all the hole co-ordinates? I mean say nhole is 10 and the 2nd hole is a escape hole for the gopher..
hmm..

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### Re: 10310 - Dog and Gopher

NEWKID,
IF NOT BREAK THE LOOP
THEN IT PRINT THE LAST ESCAPABLE HOLE.
IF MORE THEN 1 ESCAPABLE HOLE THEN WHAT SHOULD BE ANSWER????
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

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

### Re: 10310 - Dog and Gopher

oh.. thats the easy part.. you can do like this..

Code: Select all

``````typedef struct Hole {
double x, y;
}
Hole hole[MAXHOLES];
for (int i = 0; i < nholes; i++) {
scanf("%lf %lf", &hole[i].x, &hole[i].y);
}

for (int i  = 0; i < nholes; i++) {
//  if feasible with this hole then set ur flag and break..
}
``````
hmm..

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 10310 - Dog and Gopher

Can some one help me. I got TLE.. Code: Select all

``removed``
Last edited by Obaida on Tue Feb 03, 2009 9:13 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

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

### Re: 10310 - Dog and Gopher

whats the logic behind this line?

Code: Select all

``if(((dog_x>=gophar_x)&&(gophar_x>=hole_x[i]))||((dog_x<=gophar_x)&&(gophar_x<=hole_x[i]))||((dog_x-gophar_x==0)&&(((dog_y>=gophar_y)&&(gophar_y>=hole_y[i]))||((dog_y<=gophar_y)&&(gophar_y<=hole_y[i])))))``
just comment this line and you will get accepted..
hmm..

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Sorry i was kidding.    