LCC '18 Contest 1 S5 - Line Runner

View as PDF

Submit solution

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

Author:
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

2
0 0 0 1
1 0 1 1
0 0 1 1

Sample Output 1

-1

Sample Input 2

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

Sample Output 2

2.00

Comments

There are no comments at the moment.