Problem E
Intersection is not that Easy
Input: Standard Input

Output: Standard Output

Time Limit: 1 Second

 

In this problem your job is to find the distance between two lines or a line and a line segment or two line segments. Suppose we have two points A(x1,y1) and B(x2,y2) on a two dimensional Cartesian plane. If we connect A and B then we get line segment AB. But if we connect AB and extend it on both side at infinite length then we get line AB.

 

Input

The input file contains several sets of inputs. The description of each set of input is given below:

 

The description for each set of input is given in two lines. Each line contains four integers and a string. First line contains x1, y1, x2, y2 and S1 and the second line contains x3, y3, x4, y4 and S2. The value of S1 and S2 can be either “L” or “LS” which stands for “Line” and “Line-segment” respectively. (x1, y1) and (x2, y2) are the endpoints of first line segment or they are just two different points on the first line depending on the value of S1. The same story applies for the second input line for this set. Input is terminated by a set where the value of S1 and S1 is “END”. This set should not be processed. Point (x1,y1) and (x2,y2) are always different. Similarly point (x3,y3) and (x4,y4) are also always different. All the integers in the input file have absolute value less than 101.

 

Output

For each set of input you should produce one line of output which contains a single floating-point number indicating the distance between the two lines or line segments or the distance between one line and one line segment. This floating-point number contains five digits after the decimal point. Errors less than 2e-5 will be ignored.

 

Sample Input                               Output for Sample Input

10 10 20 20 L
-10 –10 19 19 L
10 10 12 13 LS
11 11 19 20 LS
10 10 12 12 END
11 11 23 34 END

0.00000

0.27735

 

Problem setter: Shahriar Manzoor, EPS.

Special Thanks: Derek Kisman, EPS.