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 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)


Comments

There are no comments at the moment.