# UVa 10709 - Intersection is Not that Easy

## Problem

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.

## Solution

• 兩線斷是否相交
• 一個點是否在線段兩端點之間 (線段上方/下方)
• 是否在線段上

• 線段與線段
• 相交，最鄰近距離 0。
• 不相交，查閱是否能作投影，否則直接查閱到端點的距離。
• 線與線
• 不平行，最鄰近距離 0。
• 平行，直接調用公式計算兩線距離。 // 當然可以調用投影距離。
• 線與線段
• 線段跨過線的兩側，最鄰近距離 0
• 同側，直接做投影。