All Tracks Problem

Street racing
Tag(s):

Algorithms, Medium

Problem
Editorial
Analytics

You are taking part in a new street racing competition in your city! Your city can be considered as N points-crossings on the plane with M segments-roads connecting some pairs of the crossings. Start is placed at crossing S and finish at crossing F. Now you want to know the minimum distance you have to cover.

But there is one issue: you can not arbitrary switch roads in crossing because your speed is very high - 1 unit / 1 second. More precisely: you can drive on the road B-C after road A-B if angle between your old direction of movement and new direction of movement is less or equal to a degrees (otherwise this turn will be very dangerous and you have a risk of getting to ditch). Initially you can move from S in any direction.

So what is the minimum distance you have to drive in order to get from S to F?

Constraints

1 <= N <= 100
0 <= M <= N * (N-1) / 2
0 <= a <= 180
-10 000 <= x, y <= 10 000
1 <= S,F <= N

Input

The first line contains 3 space-separated integers: N, M, a
The second line contains 2 space-separated integers: S, F. The following N lines contain pair of integers x, y each and describe points corresponding to the crossings. The following M lines contain pair of integers q, w each and correspond to segment-road between crossings q and w. Crossings are enumerated from 1 to N.

Output

Output the minimum distance you have to drive with exactly 3 digits after decimal point or -1 if it's impossible to get from S to F.

SAMPLE INPUT
4 4 90
1 4
0 1
1 1
1 0
0 0
1 2
2 3
3 4
1 3
SAMPLE OUTPUT
3.000
Explanation

Here, we travel from 1->2->3->4, since we cannot travel from 1->3->4, although it gives a shorter path.

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: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

September Circuits

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications