Editorial for DMOPC '19 Contest 6 P1 - Grade 9 Math
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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:
Comments