10310 - Dog and Gopher

[helloneo]

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]

so... if both reaches a role at same time, the dog eats the gopher...
that's right???

[helloneo]

so... if both reaches a role at same time, the dog eats the gopher...
that's right???

that case.. the gopher is safe..

[isagooddaytodie]

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]

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]

#include<stdio.h>
#include<math.h>
int main()
{
int n,k,temp;
double x1,y1,x2,y2;
double holeX[10000],holeY[10000];
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]

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]

Please Help..
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[1000][2];
    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][0]>>H[i][1];
    for(i=0; i<n; i++)
    {
        if(panjang(D1,D2,H[i][0],H[i][1])>2*panjang(G1,G2,H[i][0],H[i][1]))
        {
          cout<<"The gopher can escape through the hole at ("<<H[i][0]+eps<<","<<H[i][1]+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));    
}

[sazzadcsedu]

whats wrong with my code??

Code: Select all

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

              #define eps 1e-7

              double h[1001][1001];
       
               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;

			   }



	

[newkid]

@sazzadcsedu
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..

[sazzadcsedu]

NEWKID,
IF NOT BREAK THE LOOP
THEN IT PRINT THE LAST ESCAPABLE HOLE.
IF MORE THEN 1 ESCAPABLE HOLE THEN WHAT SHOULD BE ANSWER????

[newkid]

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..
}

[Obaida]

Can some one help me. I got TLE..

Code: Select all

removed

[newkid]

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..

[Obaida]

Sorry i was kidding.