## 204 - Robot Crash; unclear description?

Moderator: Board moderators

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

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.
..
A great helper

Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### 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.71067810.0 5.0 135.0 100.0`
stubbscroll
Experienced poster

Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway

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

Posts: 519
Joined: Mon Jan 23, 2006 10:45 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
polluel
New poster

Posts: 6
Joined: Tue Feb 28, 2006 4:20 pm

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

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm

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

Posts: 6
Joined: Tue Feb 28, 2006 4:20 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.
sclo
Guru

Posts: 519
Joined: Mon Jan 23, 2006 10:45 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.
polluel
New poster

Posts: 6
Joined: Tue Feb 28, 2006 4:20 pm

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

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm