## 204 - Robot Crash

Moderator: Board moderators

Sonya_b
New poster
Posts: 1
Joined: Tue Mar 08, 2005 5:26 pm

### 204 - Robot Crash

it will be that somebody has the code of this work and could in giving? debtor little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 204 - Robot Crash; unclear description?

From the problem description:
If there are multiple collisions, only print the first one. If there are multiple collisions at the same time, only print the one with smallest x-coordinate.
But what is the 'first one' if the two robots can be at the collision points at different times?

Take as an example

Code: Select all

``````0.000 1.000  45.000 10.000
5.000 1.000 116.565 10.000``````
The robots collide at two places:
(2.00, 2.00): the left robot is there at 0.2828 sec and the right robot at 0.6708 sec
(3.33, 3.33): the left robot is there at 0.4714 sec and the right robot at 0.3727 sec

But what is first in this case? The average time at the first point is 0.4768 sec, and at the second point 0.4221 sec, which would favour the second point, but the first point has the earliest time of any robot being there.
Or should we forget this whole 'first one' thing and always print the point with the smallest x-coordinate.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
My code makes this output:

Code: Select all

``````Robot Problem #1: Robots collide at (3.33,4.33)
``````
I have checked my code, for each collision, I take the later time of arrival as the time of collision, so for 0.4714 vs. 0.3727 I takes 0.4714. Don't ask me why I do that, I forget the detail already and it seems that I just get that by luck......
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

### Re: 204 - Robot Crash; unclear description?

little joey wrote:But what is the 'first one' if the two robots can be at the collision points at different times?
I think the time of the collision is when the second robot passes a point where the first robot has already passed. Even if the problem statement doesn't define "collision" in this way, the above makes sense for me. However, since I don't have AC, I can't be sure that the problemsetters' definition is the same Here's a test case with two collisions at the same time, correct answer should be (0.00,5.00).

Code: Select all

`````` 0.0 5.0   0.0  70.710678
10.0 5.0 135.0 100.0``````

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
That corresponds to minimizing the max time of the two robots at each intersection which is a collision. I got AC with it, so probably that's the correct interpretation.

polluel
New poster
Posts: 6
Joined: Tue Feb 28, 2006 4:20 pm
I'm trying to solve this problem but i don't know how to deal with:
"robots collide when they pass through the same place within 0.5 second of each other"
thanks

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
It means, consider every intersection positions of the two robots ignoring time. Then if they pass through the intersection point within 0.5 sec of each other, it would be a collision.

polluel
New poster
Posts: 6
Joined: Tue Feb 28, 2006 4:20 pm
Thanks, but i had already understood that. I meant how do you use this information? What changes have you made to your program?

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
The main idea for this problem is the compute all such collisions. We don't need to find all intersections, just find all intersections with time difference within 0.5. To find where the intersections might be, first find the x-coordinate where the two robot passes each other, then scan left and right to find collisions. Be careful with floating point errors.

polluel
New poster
Posts: 6
Joined: Tue Feb 28, 2006 4:20 pm
trying a lot of things but i can't... Last edited by polluel on Fri Mar 31, 2006 12:08 am, edited 2 times in total.

polluel
New poster
Posts: 6
Joined: Tue Feb 28, 2006 4:20 pm
could you be more explicit please. I understand but when you say scan left and right... Thanks.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
scan left and right means scanning in negative and positive x direction to find the intersections, it is what my algorithm does. I implemented some sort of scanline algorithm to find the intersections.

Darren
New poster
Posts: 1
Joined: Sun Dec 10, 2006 7:20 pm

### 204 WA

I'm getting a WA for this program. It seems to satisfy the cases in the problem text though. Can anyone tell me where it's going wrong?

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <sstream>
#include <algorithm>
#include <iostream>
#include <assert.h>
#include <float.h>
#include <set>

#define _USE_MATH_DEFINES
#include <math.h>

#ifndef M_PI
#define M_PI (3.14159265358979323846)
#endif

using namespace std;

//a robot
class Robot {
public:
Robot(double x=0.0,double y=0.0,double angle=0.0,double speed=0.0):x(x),y(y),angle(angle),speed(speed)
{
};

{
};

double x,y,angle,speed;	//angle here is in degrees
};

//location of a robot
class RobotPoint {
public:
RobotPoint(double x=0.0,double y=0.0,double time=0.0):x(x),y(y),time(time) {};

double x,y;
double time;
};

//a single straight-line path segment
class RobotPathSegment {
public:
RobotPathSegment(RobotPoint start,RobotPoint end):start(start),end(end) {};

RobotPoint start,end;
};

//a straight-line graph (a+bx)
class StraightLine {
public:
double a,b;
};

double my_hypot(double a,double b) {
return sqrt(a*a+b*b);
}

StraightLine pathsegment_to_straightline(const RobotPathSegment &segment)
{
StraightLine line;
line.b=(segment.end.y-segment.start.y)/(segment.end.x-segment.start.x);
line.a=segment.start.y-line.b*segment.start.x;
return line;
}

pair<bool,RobotPoint> pathsintersect(
const RobotPathSegment &first,
const RobotPathSegment &second
)
{
bool overlap=false;
if((first.start.x>=second.start.x-1e-7)&&(first.start.x<=second.end.x+1e-7)) {
overlap=true;
} else if((first.end.x>=second.start.x-1e-7)&&(first.end.x<=second.end.x+1e-7)) {
overlap=true;
} else if((first.start.x>=second.start.x-1e-7)&&(first.end.x<=second.end.x+1e-7)) {
overlap=true;
} else if((second.start.x>=first.start.x-1e-7)&&(second.end.x<=first.end.x+1e-7)) {
overlap=true;
}
if(!overlap) {
return make_pair(false,RobotPoint());
}
//cout << "Overlapping: "
//	<< "(" << first.start.x << "," << first.start.y << ")-"
//	<< "(" << first.end.x << "," << first.end.y << ") & "
//	<< "(" << second.start.x << "," << second.start.y << ")-"
//	<< "(" << second.end.x << "," << second.end.y << ")" << endl;
StraightLine line,origline;
origline=line=pathsegment_to_straightline(first);
origline=line=pathsegment_to_straightline(second);
//now we have
//  y0 = a0 + b0 x
//and
//  y1 = a1 + b1 x
//
//we need to find
//  y0 = y1
//
//so, move x to left of
//  a0 + b0 x = a1 + b1 x
//  b0 x - b1 x = a1 - a0
//  x = (a1 - a0) / (b0 - b1)
bool exactmatch=false;
if(::fabs(line.b-line.b)<1e-7) {
//lines are parallel, so we need to use a different technique
if(::fabs(line.a-line.a)<1e-7) {
//Lines exactly coincide. In this case,
//time will do as our Y coordinate.
exactmatch=true;
line=pathsegment_to_straightline(
RobotPathSegment(
RobotPoint(first.start.x,first.start.time,first.start.time),
RobotPoint(first.end.x,first.end.time,first.end.time)
)
);
line=pathsegment_to_straightline(
RobotPathSegment(
RobotPoint(second.start.x,second.start.time,second.start.time),
RobotPoint(second.end.x,second.end.time,second.end.time)
)
);
} else {
return make_pair(false,RobotPoint());	//no intersection
}
}
RobotPoint pt;
pt.x=(line.a-line.a)/(line.b-line.b);
pt.y=origline.a+origline.b*pt.x;
//cout << "Intersection: (" << pt.x << "," << pt.y << ")" << endl;
//now, did this fall within both segments?
double firstmin=min(first.start.x,first.end.x)-1e-7,
firstmax=max(first.start.x,first.end.x)+1e-7,
secondmin=min(second.start.x,second.end.x)-1e-7,
secondmax=max(second.start.x,second.end.x)+1e-7;
if((pt.x>=firstmin)&&(pt.x<=firstmax)&&(pt.x>=secondmin)&&(pt.x<=secondmax)) {
//cout << "Fell within both segments." << endl;
//yes, so we need to work out when it happened.
double time;
time=first.start.time+((first.end.time-first.start.time)*(pt.x-first.start.x))/(first.end.x-first.start.x);
time=second.start.time+((second.end.time-second.start.time)*(pt.x-second.start.x))/(second.end.x-second.start.x);
//cout << "Times: " << time << " and " << time << endl;
//cout << "Diff: " << ::fabs(time-time) << endl;
//according to the rules, these must be within 0.5 seconds to count as
//an intersection
if(::fabs(time-time)<=0.5) {
//cout << "Got intersection." << endl;
pt.time=max(time,time);
return make_pair(true,pt);
}
}
return make_pair(false,RobotPoint());
}

void buildpath(vector<RobotPathSegment> &path,const Robot &robot,double limitx)
{
path.clear();
RobotPoint curpt(robot.x,robot.y,0.0);
//cout << robot.x << "," << robot.y << " angle=" << robot.angle << " speed=" << robot.speed << endl;
//cout << "dirs: " << dirx << "," << diry << endl;
assert(
((dirx>0.0)&&(curpt.x<=limitx))||
((dirx<0.0)&&(curpt.x>=limitx))
);
while(
((dirx>0.0)&&(curpt.x<=limitx))||
((dirx<0.0)&&(curpt.x>=limitx))
)
{
RobotPoint newpt;
newpt.y=(diry>0.0)?10.0:0.0;
if(::fabs(diry)<1e-7) {
newpt.x=limitx+dirx;
newpt.time=curpt.time+(newpt.x-curpt.x)/robot.speed;
} else {
newpt.x=curpt.x+dirx*((newpt.y-curpt.y)/diry);
newpt.time=curpt.time+my_hypot(newpt.x-curpt.x,newpt.y-curpt.y)/robot.speed;
}
//cout << curpt.x << "," << curpt.y << "->" << newpt.x << "," << newpt.y << " @" << newpt.time << " limit=" << limitx << endl;
path.push_back(RobotPathSegment(curpt,newpt));
curpt=newpt;
diry=-diry;
}
}

{
char buffer;
fgets(buffer,sizeof(buffer)/sizeof(char),stdin);
string str=string(buffer);
if(str.length()>0) {
if(str[str.length()-1]=='\n') {
str=str.substr(0,str.length()-1);
}
}
return str;
}

{
Robot robot;
istringstream iss(line);
iss >> robot.x >> robot.y >> robot.angle >> robot.speed;
return make_pair(!iss.fail(),robot);
}

int main(int argc, char **argv)
{
int problem=1;
do {
Robot robot;
vector<RobotPathSegment> path;
bool fail=false;
for(int t=0; t<2; t++) {
pair<bool,Robot> input;
if(input.first) {
robot[t]=input.second;
} else {
fail=true;
break;
}
}
if(fail) {
break;
}
printf("Robot Problem #%d: ",problem++);
for(int t=0; t<2; t++) {
buildpath(path[t],robot[t],robot[1-t].x);
}
vector<RobotPoint> intersections;
for(int a=0; a<path.size(); a++) {
for(int b=0; b<path.size(); b++) {
pair<bool,RobotPoint> intret=pathsintersect(path[a],path[b]);
if(intret.first) {
if((intret.second.x>=robot.x)&&(intret.second.x<=robot.x)) {
intersections.push_back(intret.second);
}
}
}
}
if(intersections.empty()) {
printf("Robots do not collide.\n\n");
} else {
RobotPoint earliest(DBL_MAX,DBL_MAX,DBL_MAX);
for(int t=0; t<intersections.size(); t++) {
if(::fabs(intersections[t].time-earliest.time)<1.e-7) {
//same time, so rank on lowest X coord
if(intersections[t].x<earliest.x) {
earliest=intersections[t];
}
} else if(intersections[t].time<earliest.time) {
earliest=intersections[t];
}
}
printf("Robots collide at (%.2lf,%.2lf)\n\n",earliest.x,earliest.y);
}
} while(1);
return 0;
}
``````

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

### Re: 204 - Robot Crash

Has anyone gotten this accepted recently? I've been getting WAs recently. Anymore test cases

The problems from the 1990 world finals sure are tricky! DX

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

### Re: 204 - Robot Crash

http://www.udebug.com/UVa/204
Click "Random Input", "Go!"
Check input and AC output for thousands of problems on uDebug!