Allie In Space
All submissions for this problem are available.
Allie is an astronaut. When she was going to space she took a game with her, so that she can play around with it whenever free. The game consists of a convex circuit and a ball. The ball can move in 2 different ways.
1)Move along the circuit.
2)Move straight down under gravity.
Given the circuit design on the coordinate system and the direction of the gravity, Allie is interested in finding the minimum distance the ball will take to reach from one vertex to another.
(Note: The given coordinates may be a float value, but the vertices will lie in integer coordinates when viewed along the line of the gravity. Angle of rotation is in degrees)
- The first line of the input contains two integers N and Angle denoting the number of vertex of the polygon and the angle of the gravity. Next N lines contain two space-separated integers each — the coordinates of the polygon vertexes. The vertexes are listed in the counter-clockwise order.
- The last line contains two space-separated integers S and T — the start and the end vertexes of the sought shortest way.
- In the output print a single real number — the length of the shortest way from vertex s to vertex t. Round off the answer to 6 decimal places.
- 1 ≤ N ≤ 10^5
- 0 ≤ | Co-ordination of circuit vertex's | ≤ 10^4
- 1 ≤ S, T ≤ N
Input: 4 0 0 0 1 0 1 1 0 1 1 4 Output: 1.000000
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.