204 - Robot Crash

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

Moderator: Board moderators

r2ro
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

Re: 204 - Robot Crash

Post by r2ro » Thu Oct 16, 2014 2:50 pm

Thanks brianfry713! My answers are way off! :lol: I'm guessing most of them is because of this:
Assume that a=b only if |a-b| < ? = 10-7
For this test case:

Code: Select all

-3864.484941 0.139702 -74.881730 28.292878
-569.810049 0.363168 104.844677 34.725782
My robots do not collide according to my algorithm, but your output states that the collide at -2369.91,8.00. I'm guessing this has to be a precision issue, so any advice on how you handled those? Thanks!

r2ro
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

Re: 204 - Robot Crash

Post by r2ro » Thu Oct 23, 2014 12:31 pm

So apparently, there was an error in my calculation which got the collision incorrectly.

@brianfry713, I managed to make my program's output produce the same output as your solution in udebug, but I still get WA. :( :( Do you have anymore critical cases?

Thanks!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 204 - Robot Crash

Post by brianfry713 » Thu Oct 23, 2014 9:09 pm

Post or send me your code.
Check input and AC output for thousands of problems on uDebug!

r2ro
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

Re: 204 - Robot Crash

Post by r2ro » Sun Oct 26, 2014 12:45 pm

Hi brianfry713, I sent you my code.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 204 - Robot Crash

Post by brianfry713 » Fri Oct 31, 2014 8:41 pm

I ran your code on more random test cases and it passes them, maybe you have a small precision error or something.
Check input and AC output for thousands of problems on uDebug!

r2ro
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

Re: 204 - Robot Crash

Post by r2ro » Tue Nov 04, 2014 11:15 am

brianfry713 wrote:I ran your code on more random test cases and it passes them, maybe you have a small precision error or something.
Just a question, did you place the epsilon when you displayed the floating point numbers? As of now, I have the epsilon in the ff:

- When checking if the lines overlap ex:

Code: Select all

 ((secondGun.start.x >= firstGun.start.x-EPSILON)&&(secondGun.end.x <= firstGun.end.x + EPSILON) 
- Checking for the line distances ex:

Code: Select all

 if(fabs(line[0].b-line[1].b) < EPSILON) 
- Checking for the collision points ex:

Code: Select all

 firstGunmax=max(firstGun.start.x,firstGun.end.x)+EPSILON, 
I don't have them when I:

- Check for the x coordinate's collision point which denotes the earliest:

Code: Select all

if(finalResults[i].x < collisionPoint.x)
- Have the gun bounce around the environment:

Code: Select all

 ((dir_x > 0.0) && (current.x <= maxX)) || ((dir_x < 0.0) && (current.x >= maxX)) 
- Use to check for the time when a collision occurred:

Code: Select all

 if(fabs(time[1]-time[0]) <= MAX_TIME) 
After 203, I'm tempted to place the Epsilon just about everywhere, but then I'm not so sure. Any insights from your solution?

Thanks! :)

(BTW, I'm really sorry if I've been asking too many questions. I'm really weak at problems that require a lot of precision so I'm trying to see how I can improve at those types of problems, it just so happens that 203 and this are good examples)

r2ro
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

Re: 204 - Robot Crash

Post by r2ro » Fri Nov 07, 2014 5:31 pm

Okay, so I've decided to post my code for everyone's info, since I've been trying to solve it but the error is really mysterious and this is the last problem in the 1990 set I've got left...

A few notes to consider:

1.) I consider my algorithm not really optimized. Running it through 5000 test cases may cause it to run for a long time (but it terminates eventually), but it terminates at approx. 0.165 seconds more or less in the judge. Either the judge's test data is not something that will cause the code to run for a long time, or there are not a lot of test cases, or my program just blows in one of the earlier test cases where the judge just decides to not check the other test cases anymore, I don't know. Who knows? Maybe this is a TLE in the making. :lol:

2.) I've used a random input generator to generate different sets inputs over and over again, and they have always been the same with the output displayed in udebug.

3.) I've attached comments in the relevant places so that my code is easier to read. Just pardon the #debug parts that are littered everywhere. It's mainly just for taking in input / displaying the output onto a text file which I can use to compare with the output generated by udebug.

4.) Attached is my updated code. I've added epsilons where I think it's relevant to add them, but I'm still getting WA. Anyone who's had their code accepted, willing to tell me where my solution varies in your approach, or willing to PM me if they manage to make changes in my code to get it accepted? :)

Really, the algorithm should be straight forward, and I implemented the precision things I did for probs. #206 and #203 (thanks to brianfry713 for 203), so I can't see how different #204 should be, unless I'm missing something. :-?

Code: Select all

/****
204.cpp WA @ 0.165s

Might TLE because of precision computations...
****/

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

#define DEBUG

#ifdef DEBUG
#include <conio.h>
#endif

#define EPSILON 1e-7
#define MAX_TIME 0.5
#define RADIANS(angle) ((angle) * M_PI / 180.0 )
#define DEGREES(angle) ((angle) * 180.0 / M_PI )

using namespace std;

class Line2D
{
	public: double a,b; // a + bx
};

#ifdef DEBUG
FILE *outFile;
#endif

////// Gun INFO //////

class Gun 
{
	public: double x,y,angle,speed,angleRad,angleDeg; 
	   
    Gun(double x = 0,double y=0,double angle=0,double speed=0):
		x(x),y(y),angle(angle),speed(speed)
    {
      angleRad = RADIANS(angle);
      angleDeg = DEGREES(angle);
    };
};

class GunData 
{
	public: double x,y,time;
	GunData(double x = 0,double y = 0,double time = 0): 
		x(x),y(y),time(time) {};
};

class GunPath
{
	public: GunData start,end;
	
	GunPath(GunData start,GunData end):
		start(start),end(end) {};
};

GunData answer;

/* convert segment to line */
Line2D completeLine (GunPath lineSegment)
{
   Line2D line;
   line.b = (lineSegment.end.y - lineSegment.start.y) / (lineSegment.end.x - lineSegment.start.x);
   line.a = lineSegment.start.y - line.b * lineSegment.start.x;
   return line;
}

/* simulate the collision. If there will be a collision, true is returned and info where collision occured */
bool simulatePaths(GunPath firstGun, GunPath secondGun)
{
   bool match = false, intersect = false;

	/**** This section is used to check if they overlap with one another. There is a possibility for collision if and only if they can intersect with each other ***/
	
   if((firstGun.start.x >= secondGun.start.x-EPSILON) && (firstGun.start.x <= secondGun.end.x + EPSILON))
      intersect = true;
   else if((firstGun.end.x >= secondGun.start.x-EPSILON) && (firstGun.end.x <= secondGun.end.x + EPSILON))
      intersect = true;
   else if((firstGun.start.x >= secondGun.start.x-EPSILON) && (firstGun.end.x <=secondGun.end.x + EPSILON))
      intersect = true;
   else if((secondGun.start.x >= firstGun.start.x-EPSILON)&&(secondGun.end.x <= firstGun.end.x + EPSILON))
      intersect = true;
      
   if(!intersect)
      return false;	// Not overalapping. Impossible
	
	/** Potential to intersect? Complete the lines **/
	
   Line2D line[2],origline[2];
   line[0] = completeLine(firstGun);
   line[1] = completeLine(secondGun);
   
   origline[0] = line[0];
   origline[1] = line[1];

   match = false;
   
   if(fabs(line[0].b - line[1].b) < EPSILON) 
   {
      if(fabs(line[0].a-line[1].a)<EPSILON)	// Matches. Check now if they can collide, generate lines
	  {
         match=true;
         
         /* First Gun */
         GunData firstStart(firstGun.start.x,firstGun.start.time,firstGun.start.time);
         GunData firstEnd(firstGun.end.x,firstGun.end.time,firstGun.end.time);
         line[0] = completeLine(GunPath(firstStart,firstEnd)); // Make the complete line
         
         /* Second Gun */
         GunData secondStart(secondGun.start.x,secondGun.start.time,secondGun.start.time);
         GunData secondEnd(secondGun.end.x,secondGun.end.time,secondGun.end.time);
         line[1] = completeLine(GunPath(secondStart,secondEnd)); // Make the complete line
      } 
	  else 
         return false;   // No intersection, collision impossible
   }
   
   // Continue after making the lines//
   GunData result;
   
   result.x = (line[1].a-line[0].a) / (line[0].b-line[1].b);
   result.y = origline[0].a + origline[0].b * result.x;
   
   /*** Find the relevant points...The x coordinates. The earliest and latest of both guns ***/
   double firstGunmin = min(firstGun.start.x,firstGun.end.x),
      firstGunmax = max(firstGun.start.x,firstGun.end.x),
      secondGunmin = min(secondGun.start.x,secondGun.end.x),
      secondGunmax = max(secondGun.start.x,secondGun.end.x);
      
   if((result.x >= firstGunmin - EPSILON) && (result.x <= firstGunmax + EPSILON) && (result.x >= secondGunmin - EPSILON) && (result.x <= secondGunmax + EPSILON)) // Can they collide? Yes?
   {
      double time[2];
      time[0] = firstGun.start.time + ((firstGun.end.time - firstGun.start.time)*(result.x - firstGun.start.x)) / (firstGun.end.x - firstGun.start.x) + EPSILON;
      time[1] = secondGun.start.time + ((secondGun.end.time - secondGun.start.time)*(result.x - secondGun.start.x)) / (secondGun.end.x - secondGun.start.x) + EPSILON;
      if(fabs(time[1] - time[0]) <= MAX_TIME + EPSILON) // Only call it a collision if it occurs within the 0.5 time. Create a collision info
	  {
         result.time = max(time[0],time[1]);
         answer.x = result.x;
         answer.y = result.y;
         answer.time = result.time;
         return true;
      }
   }
   return false; // last resort, no collision. 
}

/**** This method is called from runCourse (which is right below it) ***/
double computeC (double a,double b) // a^2 + b^2 = c^2
{
   return sqrt(a*a+b*b);
}

/*** This will return a vector containing the path of our gun bouncing around the environment ***/
void runCourse(double maxX, Gun robot, vector<GunPath> &path)
{
   double deltaY, deltaX, dir_x,dir_y;
   
   path.clear();
   GunData current(robot.x,robot.y,0.0);
   
   dir_x = cos(robot.angleRad);
   dir_y = sin(robot.angleRad);
   
   while(((dir_x > 0.0 - EPSILON) && (current.x <= maxX + EPSILON)) || ((dir_x - EPSILON < 0.0) && (current.x + EPSILON >= maxX))) // Make the gun bounce around the environment
   {
      GunData newPoint;
      newPoint.y = (dir_y > 0.0 + EPSILON)?10.0:0.0;
      if(fabs(dir_y) < EPSILON) 
	  {
         newPoint.x = maxX + dir_x;
         newPoint.time = current.time + (newPoint.x - current.x) / robot.speed;
      } 
	  else 
	  {
		 deltaY = newPoint.y - current.y;
         newPoint.x = current.x + dir_x * ((deltaY)/dir_y);
         deltaX = newPoint.x - current.x;
         newPoint.time = current.time + computeC(deltaX,deltaY) / robot.speed; // See above
      }
      path.push_back(GunPath(current,newPoint));
      current = newPoint;
      dir_y = -dir_y;
   }
}

void process(Gun g1,Gun g2)
{
	int i, j, p0size, p1size, inSize;
	vector<GunPath> path[2];
	vector<GunData> finalResults;
	GunData collisionPoint (DBL_MAX,DBL_MAX,DBL_MAX);
	
	runCourse(g2.x,g1,path[0]); // Run gun 1's path
	runCourse(g1.x,g2,path[1]); // Run gun 2's path
	
	p0size = path[0].size(); // This will contain gun 1's path
	p1size = path[1].size(); // This will contain gun 2's path
	
	/*** @@@ I think this is where it's faulty ??? ***/
	for(i = 0; i < p0size; i++) 
	{
	    for(j = 0; j < p1size; j++) 
		{
            bool result = simulatePaths(path[0][i],path[1][j]); // Simulate paths and look for collision
            if(result == true) 
			{
				if((answer.x+EPSILON >= g1.x) && (answer.x <= g2.x+EPSILON))
                  finalResults.push_back(answer);
            }
	     }
	  }
	
	inSize = finalResults.size();
	
	if(finalResults.empty()) // No collision occured? :(
	{
		fprintf(stdout,"Robots do not collide.\n\n");
		#ifdef DEBUG
		fprintf(outFile,"Robots do not collide.\n\n");
		#endif
	}
	else // Yes collision occured! :)
	{
		/*** If a collision occured, we find collisionPoint, which is going to contain the earliest time / x coordinate when the robos crashed ***/
	     for(i = 0; i < inSize; i++) 
		 {
	        if(fabs(collisionPoint.time - finalResults[i].time) < EPSILON) 
			{
	           if(finalResults[i].x < collisionPoint.x - EPSILON)
	              collisionPoint = finalResults[i];
	        } 
			else if(finalResults[i].time < collisionPoint.time - EPSILON)
	           collisionPoint = finalResults[i];
	     }
	     fprintf(stdout,"Robots collide at (%.2lf,%.2lf)\n\n",collisionPoint.x+EPSILON,collisionPoint.y+EPSILON); // Find the earliest collision occurance
	     #ifdef DEBUG
	     fprintf(outFile,"Robots collide at (%.2lf,%.2lf)\n\n",collisionPoint.x+EPSILON,collisionPoint.y+EPSILON);
	     #endif
	}
}

int main()
{
   int problem=1;
   double a1, a2, a3, a4;
   
   #ifdef DEBUG
   outFile = fopen("output.txt","wt");
   freopen ("input.txt","rt",stdin);
   #endif
   while (fscanf(stdin,"%lf %lf %lf %lf",&a1,&a2,&a3,&a4) != EOF)
   {
      Gun g1(a1,a2,a3,a4);
      fscanf(stdin,"%lf %lf %lf %lf",&a1,&a2,&a3,&a4);
      Gun g2(a1,a2,a3,a4);
      fprintf(stdout,"Robot Problem #%d: ",problem);
      #ifdef DEBUG
      fprintf(outFile,"Robot Problem #%d: ",problem);
      #endif
      problem++;
      process(g1,g2); // Meat of the program
   }
   #ifdef DEBUG
   fclose(outFile);
   #endif
   //getch();
   return 0;
}
Thanks in advance for anyone who can help!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 204 - Robot Crash

Post by lighted » Fri Nov 07, 2014 7:41 pm

Just pardon the #debug parts that are littered everywhere. It's mainly just for taking in input / displaying the output onto a text file which I can use to compare with the output generated by udebug.
Instead of your "DEBUG", you could add this part at the beginning to work with files and send your code to judge without removing that part. It would make your code more clear

Code: Select all

#ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
#endif
You can check I/O here. http://contest.mff.cuni.cz/old/archive/ ... nl1989.tgz
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

r2ro
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

Re: 204 - Robot Crash

Post by r2ro » Sat Nov 08, 2014 3:01 am

Haha, thanks lighted. Although, I decided to do that because I wanted it to output to both the console and a separate file for this particular problem due to the fact that it can take a while for my code to run through 5000 lines of input, depending on the values produced by the random input generator. This is so that I can monitor what is being displayed on the console and the output file at the same time (under normal circumstances, I don't do this). When I submit to the OJ, I just commented out the #define DEBUG part.

And I also looked at the solutions / sample I/O of the set included there, but it seems that both the solution(s) and output(s) particularly of certain problems (this included) is faulty. I've been using the sample I/O along with the input generator of that particular set, and my output matches those of udebug. (But not those of the solution included in the set, which is wrong anyway)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 204 - Robot Crash

Post by brianfry713 » Tue Nov 11, 2014 8:52 pm

I believe the judge runs the entire input before checking the output. So if you get WA your code is running fast enough for the entire judge's input.
Check input and AC output for thousands of problems on uDebug!

r2ro
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

Re: 204 - Robot Crash

Post by r2ro » Mon Nov 17, 2014 12:40 pm

This precision error is driving me nuts... :lol:

@brianfry713: Any hint as to how you handled the precision issue? I'm really itching to get this AC since I think I'm really close already. Out of the several judge test cases, I think there is just one where I fail at. (Just one, which is either a mess up in the collision coordinates & determining more precisely or the final value display, my guess is the former)

Code: Select all

/****
204 - Robot Crash
****/

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

//#define DEBUG

#ifdef DEBUG
#include <conio.h>
#endif

#define EPSILON 1e-7
#define MAX_TIME 0.5
#define RADIANS(angle) ((angle) * M_PI / 180.0 )
#define DEGREES(angle) ((angle) * 180.0 / M_PI )

using namespace std;

class Line2D
{
   public: double a,b; // a + bx
};

#ifdef DEBUG
FILE *outFile;
#endif

////// Gun INFO //////

class Gun 
{
   public: double x,y,angle,speed,angleRad,angleDeg; 
      
    Gun(double x = 0,double y=0,double angle=0,double speed=0):
      x(x),y(y),angle(angle),speed(speed)
    {
      angleRad = RADIANS(angle);
      angleDeg = DEGREES(angle);
    };
};

class GunData 
{
   public: double x,y,time;
   GunData(double x = 0,double y = 0,double time = 0): 
      x(x),y(y),time(time) {};
};

class GunPath
{
   public: GunData start,end;
   
   GunPath(GunData start,GunData end):
      start(start),end(end) {};
};

GunData answer;

/* convert segment to line */
Line2D completeLine (GunPath lineSegment)
{
   Line2D line;
   line.b = (lineSegment.end.y - lineSegment.start.y) / (lineSegment.end.x - lineSegment.start.x);
   line.a = lineSegment.start.y - line.b * lineSegment.start.x;
   return line;
}

/* simulate the collision. If there will be a collision, true is returned and info where collision occured */
bool simulatePaths(GunPath firstGun, GunPath secondGun)
{
   bool match = false, intersect = false;

   /**** This section is used to check if they overlap with one another. There is a possibility for collision if and only if they can intersect with each other ***/
   
   if((firstGun.start.x >= secondGun.start.x-EPSILON) && (firstGun.start.x <= secondGun.end.x + EPSILON))
      intersect = true;
   else if((firstGun.end.x >= secondGun.start.x-EPSILON) && (firstGun.end.x <= secondGun.end.x + EPSILON))
      intersect = true;
   else if((firstGun.start.x >= secondGun.start.x-EPSILON) && (firstGun.end.x <=secondGun.end.x + EPSILON))
      intersect = true;
   else if((secondGun.start.x >= firstGun.start.x-EPSILON)&&(secondGun.end.x <= firstGun.end.x + EPSILON))
      intersect = true;
      
   if(!intersect)
      return false;   // Not overalapping. Impossible
   
   /** Potential to intersect? Complete the lines **/
   
   Line2D line[2],origline[2];
   line[0] = completeLine(firstGun);
   line[1] = completeLine(secondGun);
   
   origline[0] = line[0];
   origline[1] = line[1];

   match = false;
   
   if(fabs(line[0].b - line[1].b) < EPSILON) 
   {
      if(fabs(line[0].a-line[1].a)<EPSILON)   // Matches. Check now if they can collide, generate lines
     {
         match=true;
         
         /* First Gun */
         GunData firstStart(firstGun.start.x,firstGun.start.time,firstGun.start.time);
         GunData firstEnd(firstGun.end.x,firstGun.end.time,firstGun.end.time);
         line[0] = completeLine(GunPath(firstStart,firstEnd)); // Make the complete line
         
         /* Second Gun */
         GunData secondStart(secondGun.start.x,secondGun.start.time,secondGun.start.time);
         GunData secondEnd(secondGun.end.x,secondGun.end.time,secondGun.end.time);
         line[1] = completeLine(GunPath(secondStart,secondEnd)); // Make the complete line
      } 
     else 
         return false;   // No intersection, collision impossible
   }
   
   // Continue after making the lines//
   GunData result;
   
   result.x = (line[1].a-line[0].a) / (line[0].b-line[1].b);
   result.y = origline[0].a + origline[0].b * result.x;
   
   /*** Find the relevant points...The x coordinates. The earliest and latest of both guns ***/
   double firstGunmin = min(firstGun.start.x,firstGun.end.x),
      firstGunmax = max(firstGun.start.x,firstGun.end.x),
      secondGunmin = min(secondGun.start.x,secondGun.end.x),
      secondGunmax = max(secondGun.start.x,secondGun.end.x);
      
   if((result.x >= firstGunmin - EPSILON) && (result.x <= firstGunmax + EPSILON) && (result.x >= secondGunmin - EPSILON) && (result.x <= secondGunmax + EPSILON)) // Can they collide? Yes?
   {
      double time[2];
      time[0] = firstGun.start.time + ((firstGun.end.time - firstGun.start.time)*(result.x - firstGun.start.x)) / (firstGun.end.x - firstGun.start.x) + EPSILON;
      time[1] = secondGun.start.time + ((secondGun.end.time - secondGun.start.time)*(result.x - secondGun.start.x)) / (secondGun.end.x - secondGun.start.x) + EPSILON;
      if(fabs(time[1] - time[0]) <= MAX_TIME + EPSILON) // Only call it a collision if it occurs within the 0.5 time. Create a collision info
     {
         result.time = max(time[0],time[1]);
         answer.x = result.x;
         answer.y = result.y;
         answer.time = result.time;
         return true;
      }
   }
   return false; // last resort, no collision. 
}

/**** This method is called from runCourse (which is right below it) ***/
double computeC (double a,double b) // a^2 + b^2 = c^2
{
   return sqrt(a*a+b*b);
}

/*** This will return a vector containing the path of our gun bouncing around the environment ***/
void runCourse(double maxX, Gun robot, vector<GunPath> &path)
{
   double deltaY, deltaX, dir_x,dir_y;
   
   path.clear();
   GunData current(robot.x,robot.y,0.0);
   
   dir_x = cos(robot.angleRad);
   dir_y = sin(robot.angleRad);
   
   while(((dir_x > 0.0 - EPSILON) && (current.x <= maxX + EPSILON)) || ((dir_x - EPSILON < 0.0) && (current.x + EPSILON >= maxX))) // Make the gun bounce around the environment
   {
      GunData newPoint;
      newPoint.y = (dir_y > 0.0 + EPSILON)?10.0:0.0;
      if(fabs(dir_y) < EPSILON) 
     {
         newPoint.x = maxX + dir_x;
         newPoint.time = current.time + (newPoint.x - current.x) / robot.speed;
      } 
     else 
     {
       deltaY = newPoint.y - current.y;
         newPoint.x = current.x + dir_x * ((deltaY)/dir_y);
         deltaX = newPoint.x - current.x;
         newPoint.time = current.time + computeC(deltaX,deltaY) / robot.speed; // See above
      }
      path.push_back(GunPath(current,newPoint));
      current = newPoint;
      dir_y = -dir_y;
   }
}

void process(Gun g1,Gun g2)
{
   int i, j, p0size, p1size, inSize;
   vector<GunPath> path[2];
   vector<GunData> finalResults;
   GunData collisionPoint (DBL_MAX,DBL_MAX,DBL_MAX);
   
   runCourse(g2.x,g1,path[0]); // Run gun 1's path
   runCourse(g1.x,g2,path[1]); // Run gun 2's path
   
   p0size = path[0].size(); // This will contain gun 1's path
   p1size = path[1].size(); // This will contain gun 2's path
   
   /*** @@@ I think this is where it's faulty ??? ***/
   for(i = 0; i < p0size; i++) 
   {
       for(j = 0; j < p1size; j++) 
      {
            bool result = simulatePaths(path[0][i],path[1][j]); // Simulate paths and look for collision
            if(result == true) 
         {
            if((answer.x+EPSILON >= g1.x) && (answer.x <= g2.x+EPSILON))
                  finalResults.push_back(answer);
            }
        }
     }
   
   inSize = finalResults.size();
   
   if(finalResults.empty()) // No collision occured? :(
   {
      fprintf(stdout,"Robots do not collide.\n\n");
      #ifdef DEBUG
      fprintf(outFile,"Robots do not collide.\n\n");
      #endif
   }
   else // Yes collision occured! :)
   {
      /*** If a collision occured, we find collisionPoint, which is going to contain the earliest time / x coordinate when the robos crashed ***/
        for(i = 0; i < inSize; i++) 
       {
           if(fabs(collisionPoint.time - finalResults[i].time) < EPSILON) 
         {
              if(finalResults[i].x < collisionPoint.x - EPSILON)
                 collisionPoint = finalResults[i];
           } 
         else if(finalResults[i].time < collisionPoint.time - EPSILON)
              collisionPoint = finalResults[i];
        }
        fprintf(stdout,"Robots collide at (%.2lf,%.2lf)\n\n",collisionPoint.x+EPSILON,collisionPoint.y+EPSILON); // Find the earliest collision occurance
        #ifdef DEBUG
        fprintf(outFile,"Robots collide at (%.2lf,%.2lf)\n\n",collisionPoint.x+EPSILON,collisionPoint.y+EPSILON);
        #endif
   }
}

int main()
{
   int problem=1;
   double a1, a2, a3, a4;
   
   #ifdef DEBUG
   outFile = fopen("output.txt","wt");
   freopen ("input.txt","rt",stdin);
   #endif
   while (fscanf(stdin,"%lf %lf %lf %lf",&a1,&a2,&a3,&a4) != EOF)
   {
      Gun g1(a1,a2,a3,a4);
      fscanf(stdin,"%lf %lf %lf %lf",&a1,&a2,&a3,&a4);
      Gun g2(a1,a2,a3,a4);
      fprintf(stdout,"Robot Problem #%d: ",problem);
      #ifdef DEBUG
      fprintf(outFile,"Robot Problem #%d: ",problem);
      #endif
      problem++;
      process(g1,g2); // Meat of the program
   }
   #ifdef DEBUG
   fclose(outFile);
   #endif
   //getch();
   return 0;
}

LlatzerandToni
New poster
Posts: 15
Joined: Sun Apr 23, 2006 1:35 pm

Re: 204 - Robot Crash

Post by LlatzerandToni » Thu May 14, 2015 2:43 pm

I think I am also facing a precision problem.

For the following input:

Code: Select all

0 0.00000001 0.000001 10
1 0 -180 10
0 0.00000001 0.000001 10
10 0 -180 10
0 0.00000001 0.000001 10
100 0 -180 10
My code outputs:

Code: Select all

Robot Problem #1: Robots collide at (0.50,0.00)

Robot Problem #2: Robots collide at (5.00,0.00)

Robot Problem #3: Robots do not collide.
While uDebug says:

Code: Select all

Robot Problem #1: Robots collide at (0.50,0.00)

Robot Problem #2: Robots do not collide.

Robot Problem #3: Robots do not collide.
I checked the distance between robots at collision point and I have the following:

Code: Select all

1.87266e-008
9.72665e-008
8.82665e-007
So, I don't understand why the Problem #2 don't collide. Anyone with AC code can check what is the correct condition?

Thank you.
Lol

Post Reply

Return to “Volume 2 (200-299)”