## Editorial for DMOPC '19 Contest 6 P1 - Grade 9 Math

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Tzak

As vertical lines have to be considered, it is best to avoid slope-intercept form and instead use the standard form of the line to describe the lines in the input. To determine the coefficients , , and describing the line from and , consider how the terms and would be determined in slope-intercept form :

By definition, :

Then, substituting and :

Solving for :

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

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

Comparing this with the expanded point-slope from before, it is seen that: , , and .

If two lines are parallel, in their slope-intercept forms, meaning or equivalently, in their standard forms.

If two lines are coincident, they must be parallel and have in their slope-intercept forms, meaning that or equivalently, in their standard forms. Otherwise, they will intersect at one unique point.

To find the x-coordinate of the intersection, multiply by to get , and by to get . Then, subtract the second equation from the first, and solve for x:

The same process can be applied to cancel the term and find .

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: