204 - Robot Crash

[Sonya_b]

it will be that somebody has the code of this work and could in giving? debtor

[little joey]

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.

[..]

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

[stubbscroll]

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]

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]

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"
Could anybody help me please?
thanks

[sclo]

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]

Thanks, but i had already understood that. I meant how do you use this information? What changes have you made to your program?

[sclo]

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]

trying a lot of things but i can't...

[polluel]

could you be more explicit please. I understand but when you say scan left and right... Thanks.

[sclo]

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]

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)
	{
		MakeAngleRad();
	};

	void MakeAngleRad()
	{
		anglerad=(angle*M_PI)/180.0;
	};

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

//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[2],origline[2];
	origline[0]=line[0]=pathsegment_to_straightline(first);
	origline[1]=line[1]=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[0].b-line[1].b)<1e-7) {
		//lines are parallel, so we need to use a different technique
		if(::fabs(line[0].a-line[1].a)<1e-7) {
			//Lines exactly coincide. In this case,
			//time will do as our Y coordinate.
			exactmatch=true;
			line[0]=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[1]=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[1].a-line[0].a)/(line[0].b-line[1].b);
	pt.y=origline[0].a+origline[0].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[2];
		time[0]=first.start.time+((first.end.time-first.start.time)*(pt.x-first.start.x))/(first.end.x-first.start.x);
		time[1]=second.start.time+((second.end.time-second.start.time)*(pt.x-second.start.x))/(second.end.x-second.start.x);
		//cout << "Times: " << time[0] << " and " << time[1] << endl;
		//cout << "Diff: " << ::fabs(time[1]-time[0]) << endl;
		//according to the rules, these must be within 0.5 seconds to count as
		//an intersection
		if(::fabs(time[1]-time[0])<=0.5) {
			//cout << "Got intersection." << endl;
			pt.time=max(time[0],time[1]);
			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);
	double dirx=cos(robot.anglerad);
	double diry=sin(robot.anglerad);
	//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;
	}
}

string readinputline()
{
	char buffer[200];
	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;
}

pair<bool,Robot> readrobot()
{
	string line=readinputline();
	Robot robot;
	istringstream iss(line);
	iss >> robot.x >> robot.y >> robot.angle >> robot.speed;
	robot.MakeAngleRad();
	return make_pair(!iss.fail(),robot);
}

int main(int argc, char **argv)
{
	int problem=1;
	do {
		Robot robot[2];
		vector<RobotPathSegment> path[2];
		bool fail=false;
		for(int t=0; t<2; t++) {
			pair<bool,Robot> input;
			input=readrobot();
			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[0].size(); a++) {
			for(int b=0; b<path[1].size(); b++) {
				pair<bool,RobotPoint> intret=pathsintersect(path[0][a],path[1][b]);
				if(intret.first) {
					if((intret.second.x>=robot[0].x)&&(intret.second.x<=robot[1].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]

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]

http://www.udebug.com/UVa/204
Click "Random Input", "Go!"