ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1359. Construction

How to solve this one?
Posted by Douglas Cardoso 25 Jun 2010 11:39
I really couldn't figure out how to solve it. The way I tried even gives the wrong output for the sample! I modelled like this:

Each integer coordinates point represents a node of a graph. There is a edge form point (a, b) to (c, d) iff a >= c and b > d. The edge's weight is equal to the time to go from one point to another one adjacent to the first, which is calculated like this:

if theta is the angle between the segment (a, b)-(c, d) and the x-axis, then due to the gravity there is a 10*cos(theta) acceleration in the x-axis direction. So the time needed to go from (a, b) to (c, d) is sqrt(2*(c-a)/(10*cos(theta))).

Finally, what I do is to run a shortest-path algorithm in this graph. But for the sample my program answers 0.752121.

Does any one knows if ignored any detail? Or maybe if my entire model is wrong?