All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

The Maze Runner
Tag(s):

Geometry, Medium, Two dimensional

Problem
Editorial
Analytics

See Russian translation

One more nightmare... This time you got into a maze.

The maze is described by two polylines. Each of them has N + 1 points. The points of the first polyline are: (x0, y0), (x2, y2), ... , (xN, yN). The points of the second polyline are (x0, y0 + H), (x2, y2 + H), ... , (xN, yN + H).

The entrance to the maze is a segment (x0, y0) - (x0, y0 + H) and the exit is a segment (x0, y0) - (xN, yN + H). During your running in the maze you can be in any point inside the maze.

The faster you go through the maze - the more chances to survive you have. You know description of the the maze. Find the length of the shortest path you have to run.

Input
The first line contains one integer N.
The following N + 1 lines contains 2 space-separated integers each - description of the first polyline.
The last line contains one integer H.

Output
Ouput one real number with exactly 10 digits after dot - the shortest distance you have to cover.

Constraints

  • 1 <= N <= 100
  • |xi|, |yi|, H <= 104
  • x0 < x1 < ... < xN
SAMPLE INPUT
2
0 0
2 2
3 -1
2
SAMPLE OUTPUT
3.4142135624
Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

Code Monk (Computational Geometry)

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?