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

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

204 - Robot Crash

Post by Sonya_b » Tue Mar 08, 2005 7:10 pm

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

204 - Robot Crash; unclear description?

Post by little joey » Fri Mar 18, 2005 2:18 pm

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

Post by .. » Mon Mar 21, 2005 8:22 pm

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:
  • Please make discussion about the algorithm BRFORE posting source code.
    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?

Post by stubbscroll » Fri Jun 03, 2005 5:23 pm

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Mar 17, 2006 4:56 am

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

Post by polluel » Mon Mar 27, 2006 11:32 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"
Could anybody help me please?
thanks

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Mar 28, 2006 10:28 am

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

Post by polluel » Wed Mar 29, 2006 12:06 am

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Thu Mar 30, 2006 8:07 pm

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

Post by polluel » Thu Mar 30, 2006 11:20 pm

trying a lot of things but i can't... :x
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

Post by polluel » Fri Mar 31, 2006 12:07 am

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Mar 31, 2006 5:19 am

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

Post by Darren » Sun Dec 10, 2006 7:25 pm

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
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

Re: 204 - Robot Crash

Post by r2ro » Tue Sep 30, 2014 1:38 pm

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

Post by brianfry713 » Tue Sep 30, 2014 8:43 pm

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

Post Reply

Return to “Volume 2 (200-299)”