OJ Board

Code: Select all

0.000 1.000  45.000 10.000
5.000 1.000 116.565 10.000

Code: Select all

Robot Problem #1: Robots collide at (3.33,4.33)

Code: Select all

 0.0 5.0   0.0  70.710678
10.0 5.0 135.0 100.0

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;
}