204 - Robot Crash; unclear description?

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