ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
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?

Thanks!