About Love...

Time limit2sMemory limit1024 MB

Summary

Two moving line segments drift at constant velocities; find the earliest time they touch, or report -1 if they never do.

Level: Hard8 of 10
Topics: Geometry, Binary search, Math, Implementation
Solved: No attempts yet

Problem

A spider and a spideress are floating across a lake on two twigs. They cannot swim, so they can meet only when the twigs touch.

Assume the twigs are line segments and move at constant velocities. Determine how long the unfortunate arthropods must wait to meet.

Input

The input file contains 12 numbers: $x_1$ , $y_1$ , $x_2$ , $y_2$ , $x_3$ , $y_3$ , $x_4$ , $y_4$ , $v_{1x}$ , $v_{1y}$ , $v_{2x}$ , $v_{2y}$ . The endpoints of the first segment are $(x_1, y_1)$ and $(x_2, y_2)$ , the endpoints of the second segment are $(x_3, y_3)$ and $(x_4, y_4)$ , the velocity of the first segment is $(v_{1x}, v_{1y})$ , and the velocity of the second segment is $(v_{2x}, v_{2y})$ . All numbers are integers with absolute value at most $10^4$ . At the initial moment the twigs do not touch.

It is guaranteed that the twigs have nonzero length.

Output

Print the time until the earliest moment when the twigs touch, with an error of at most $10^{-4}$ . If the twigs never touch, print $-1$ .

Examples2

Example 1
Input
```
0 0 -1 3
4 4 7 7
3 0
0 -1
```
Expected output
```
1.6
```
Example 2
Input
```
0 0 -1 3
4 4 7 7
1 0
0 -3
```
Expected output
```
-1
```