As vertical lines have to be considered, it is best to avoid slope-intercept form and instead use the standard form of the line ~Ax+By+C=0~ to describe the lines in the input. To determine the coefficients ~A~, ~B~, and ~C~ describing the line from ~(x_1,y_1)~ and ~(x_2,y_2)~, consider how the terms ~m~ and ~b~ would be determined in slope-intercept form ~y=mx+b~:

By definition, ~m=\frac{y_2-y_1}{x_2-x_1}~:

$$\displaystyle y=\frac{y_2-y_1}{x_2-x_1}x+b$$

Then, substituting ~y=y_1~ and ~x=x_1~:

$$\displaystyle y_1=\frac{(y_2-y_1)x_1}{x_2-x_1}+b$$

Solving for ~b~:

$$\displaystyle b=y_1-\frac{(y_2-y_1)x_1}{x_2-x_1}=\frac{(x_2-x_1)y_1-(y_2-y_1)x_1}{x_2-x_1}$$

Putting this together gives the equation which describes the slope-intercept form of a line from two points:

$$\displaystyle y=\frac{y_2-y_1}{x_2-x_1}x+\frac{(x_2-x_1)y_1-(y_2-y_1)x_1}{x_2-x_1}$$

Now, rearrange the standard form of the line in terms of ~y~:

$$\displaystyle \begin{align} By &= -Ax-C \\ y &= \frac{-A}{B}x+\frac{-C}{B} \end{align}$$

Comparing this with the expanded point-slope from before, it is seen that: ~A=y_1-y_2~, ~B=x_2-x_1~, and ~C=-(Ax_1+By_1)~.

If two lines are parallel, ~m_1=m_2~ in their slope-intercept forms, meaning ~\frac{-A_1}{B_1}=\frac{-A_2}{B_2}~ or equivalently, ~A_1B_2=A_2B_1~ in their standard forms.

If two lines are coincident, they must be parallel and have ~b_1=b_2~ in their slope-intercept forms, meaning that ~\frac{-C_1}{B_1}=\frac{-C_2}{B_2}~ or equivalently, ~B_1C_2=B_2C_1~ in their standard forms. Otherwise, they will intersect at one unique point.

To find the x-coordinate of the intersection, multiply ~A_1x+B_1y+C_1=0~ by ~B_2~ to get ~B_2A_1x+B_2B_1y+B_2C_1=0~, and ~A_2x+B_2y+C_2=0~ by ~B_1~ to get ~B_1A_2x+B_1B_2y+B_1C_2=0~. Then, subtract the second equation from the first, and solve for x:

$$\displaystyle \begin{align} B_2A_1x-B_1A_2x+B_2C_1-B_1C_2 &= 0 \\ x &= \frac{B_1C_2-B_2C_1}{B_2A_1-B_1A_2} \end{align}$$

The same process can be applied to cancel the ~Ax~ term and find ~y=\frac{A_1C_2-A_2C_1}{A_2B_1-A_1B_2}~.

Pseudocode:

read x1, y1, x2, y2, x3, y3, x4, y4
A1 is y1 - y2, B1 is x2 - x1, C1 is -(A1 * X1 + B1 * Y1)
A2 is y3 - y4, B2 is x4 - x3, C2 is -(A2 * X3 + B2 * Y3)
if A1 * B2 == A2 * B1
    if B1 * C2 == B2 * C1 print "coincident"
    else print "parallel"
else
    x is (B1 * C2 - B2 * C1) / (B2 * A1 - B1 * A2)
    y is (A1 * C2 - A2 * C1) / (A2 * B1 - A1 * B2)

Time complexity: ~\mathcal O(1)~