LCC '18 Contest 1 S5 - Line Runner

Submit solution

Points: 20
Time limit: 3.0s
Memory limit: 256M

Problem types

Eli is playing a game where she can draw a number of lines in the plane and then, starting at a point on one of her lines, she can move along the lines that she drew in any direction.

Eli has just created a level in this game by drawing \(N\) straight line segments and picking two points on her drawing. She then has to move from one of the points to the other by following the lines. Eli would like your help to figure out the shortest distance that she must travel to get from one point to the other.

Input Specification

The first line of input contains an integer \(N\) \((1 \le N \le 300)\), the number of line segments that Eli has drawn. The next \(N\) lines each contain four integers \(A_i, B_i, C_i, D_i\) \((-10^4 \le A_i, B_i, C_i, D_i \le 10^4)\), representing a line segment from point \((A_i, B_i)\) to a point \((C_i, D_i)\). The last line contains four integers \(X_1, Y_1, X_2, Y_2\) \((-10^4 \le X_1, Y_1, X_2, Y_2 \le 10^4)\), the two points.

Output Specification

The minimum distance that a player must travel along the lines to get from one point to the other. Your answer will be considered correct if it has an absolute or relative error of at most \(10^{-6}\). If it is impossible to travel from one point to the other, output -1.

Sample Input 1

0 0 0 1
1 0 1 1
0 0 1 1

Sample Output 1


Sample Input 2

0 0 2 0
1 -1 1 2
1 1 0 0

Sample Output 2



There are no comments at the moment.