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