CF703C Chris and Road
Solution Sketch
Key idea
Think of the slope of the line $m = \frac{u}{v}$. What can you do with it?
Observation
If you draw the polygon out on the Cartesian coordinate plane and draw a line $y = mx$, you will figure out that if the line never intersects with the polygon, you won’t be hit by the bus!
Otherwise, find the rightmost line using the same slope ($m = \frac{u}{v}$) by iterating over all vertices, and use the value $b$ from the rightmost line ($y = mx + b$) to calculate the minimal time to walk to the target, which is $ \frac{(w - b)}{u} $.
AC Code
|
|