Editorial for DMOPC '19 Contest 6 P1 - Grade 9 Math - Olympiads Online Judge

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$ $A x + B y + C = 0$ to describe the lines in the input. To determine the coefficients $A$ $A$ , $B$ $B$ , and $C$ $C$ describing the line from $(x_1,y_1)$ $(x_{1}, y_{1})$ and $(x_2,y_2)$ $(x_{2}, y_{2})$ , consider how the terms $m$ $m$ and $b$ $b$ would be determined in slope-intercept form $y=mx+b$ $y = m x + b$ :

By definition, $m=\frac{y_2-y_1}{x_2-x_1}$ $m = \frac{y_{2} - y_{1}}{x_{2} - x_{1}}$ :

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

Then, substituting $y=y_1$ $y = y_{1}$ and $x=x_1$ $x = x_{1}$ :

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

Solving for $b$ $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}$ $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}$ $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$ $y$ :

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

Comparing this with the expanded point-slope from before, it is seen that: $A=y_1-y_2$ $A = y_{1} - y_{2}$ , $B=x_2-x_1$ $B = x_{2} - x_{1}$ , and $C=-(Ax_1+By_1)$ $C = - (A x_{1} + B y_{1})$ .

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

If two lines are coincident, they must be parallel and have $b_1=b_2$ $b_{1} = b_{2}$ in their slope-intercept forms, meaning that $\frac{-C_1}{B_1}=\frac{-C_2}{B_2}$ $\frac{- C_{1}}{B_{1}} = \frac{- C_{2}}{B_{2}}$ or equivalently, $B_1C_2=B_2C_1$ $B_{1} C_{2} = B_{2} C_{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$ $A_{1} x + B_{1} y + C_{1} = 0$ by $B_2$ $B_{2}$ to get $B_2A_1x+B_2B_1y+B_2C_1=0$ $B_{2} A_{1} x + B_{2} B_{1} y + B_{2} C_{1} = 0$ , and $A_2x+B_2y+C_2=0$ $A_{2} x + B_{2} y + C_{2} = 0$ by $B_1$ $B_{1}$ to get $B_1A_2x+B_1B_2y+B_1C_2=0$ $B_{1} A_{2} x + B_{1} B_{2} y + B_{1} C_{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}$ $\begin{aligned} B_{2} A_{1} x - B_{1} A_{2} x + B_{2} C_{1} - B_{1} C_{2} & = 0 \\ x & = \frac{B_{1} C_{2} - B_{2} C_{1}}{B_{2} A_{1} - B_{1} A_{2}} \end{aligned}$

The same process can be applied to cancel the $Ax$ $A x$ term and find $y=\frac{A_1C_2-A_2C_1}{A_2B_1-A_1B_2}$ $y = \frac{A_{1} C_{2} - A_{2} C_{1}}{A_{2} B_{1} - A_{1} B_{2}}$ .

Pseudocode:

Copy

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)$ $O (1)$

Comments

There are no comments at the moment.