CF 102697065 - Intersection of Two Lines

Each line is given in the form [ y = mx + b ] where (m) is its slope and (b) is its (y)-intercept. The input contains the two coefficients of the first line on one row and the two coefficients of the second line on the next row.

codeforcescompetitive-programming

CF 102697065 - Intersection of Two Lines

Rating: -
Tags: -
Solve time: 51s
Verified: yes

Solution

Problem Understanding

Each line is given in the form

[ y = mx + b ]

where (m) is its slope and (b) is its (y)-intercept. The input contains the two coefficients of the first line on one row and the two coefficients of the second line on the next row.

The task is to find the (x)-coordinate of the point where the two lines intersect. The problem guarantees that the two lines do intersect, so we do not need to handle parallel lines or identical lines.

The published problem uses a one-second time limit and 256 MB of memory. There is no large (n), array, graph, or repeated test-case parameter here. The input contains only four floating-point values, so the intended solution should perform a constant number of arithmetic operations. Any algorithm whose running time depends on trying many possible (x)-coordinates is unnecessary.

The main edge cases come from the algebra rather than input size. First, the intersection can have a negative (x)-coordinate. For example,

5 3
-6 -20

produces

-2.090909090909091

because the lines intersect to the left of the (y)-axis. An implementation that assumes the answer must be non-negative would be incorrect.

A second case is when the slopes are very close to each other. For example,

1.000001 2
1 1

has

[ x = \frac{1-2}{1.000001-1} = -1000000. ]

The denominator is small, so rounding the slopes too aggressively before performing the division can significantly change the answer.

A third case is when one or both intercepts are zero. For example,

2 0
-1 3

gives

[ 2x=-x+3, ]

so (x=1). A solution that treats zero as a missing value or relies on special handling for nonzero intercepts would fail unnecessarily.

Finally, the two slopes cannot be equal under the problem's intersection guarantee. If both lines had slope (2), for example,

2 1
2 5

would represent parallel lines and would have no intersection. We do not need to invent an output for this case because the statement guarantees that every supplied pair of lines intersects.

Approaches

A brute-force approach could search for an (x)-coordinate numerically. For a chosen precision (\varepsilon), we could evaluate both lines at successive (x)-values and look for a point where their (y)-values become sufficiently close. This works conceptually because two intersecting lines have equal (y)-values exactly at their intersection.

The problem is that this turns a direct algebraic question into an arbitrary numerical search. If the search covers an interval of length (R) with spacing (\varepsilon), it requires

[ \left\lceil\frac{R}{\varepsilon}\right\rceil+1 ]

candidate evaluations in the worst case. The statement supplies no finite search interval or required discretization that would make such a method preferable. Worse, making (\varepsilon) smaller increases the operation count without giving the exact algebraic answer.

The key observation is that at the intersection, both equations have the same (y)-value. If the lines are

[ y=m_1x+b_1 ]

and

[ y=m_2x+b_2, ]

we can simply set their right-hand sides equal:

[ m_1x+b_1=m_2x+b_2. ]

Moving the (x)-terms to one side and the constants to the other gives

[ (m_1-m_2)x=b_2-b_1. ]

Since the lines are guaranteed to intersect, (m_1-m_2\neq0), so

[ x=\frac{b_2-b_1}{m_1-m_2}. ]

The brute-force works because it searches for exactly this equality numerically, but fails to exploit the fact that the equality can be solved directly. The algebra reduces the entire problem to one subtraction for the numerator, one subtraction for the denominator, and one division.

Approach Time Complexity Space Complexity Verdict
Brute Force (O(R/\varepsilon)) (O(1)) Too slow and precision-dependent
Optimal (O(1)) (O(1)) Accepted

Algorithm Walkthrough

  1. Read (m_1) and (b_1), the slope and intercept of the first line, and (m_2) and (b_2), the corresponding values for the second line.
  2. Set the two line equations equal because the (y)-coordinate is the same at their intersection.

[ m_1x+b_1=m_2x+b_2. ] 3. Rearrange the equation to isolate (x).

[ (m_1-m_2)x=b_2-b_1. ]

The problem guarantees an intersection, so the slopes cannot be equal. Division by (m_1-m_2) is consequently valid. 4. Compute

[ x=\frac{b_2-b_1}{m_1-m_2}. ] 5. Print the resulting floating-point value. Python's floating-point representation is sufficient for this problem, and Python's str conversion prints a suitable decimal representation without requiring us to choose an arbitrary number of decimal places.

The key invariant is the equation obtained by equating the two lines. At every point that can be the intersection, both expressions for (y) must have the same value. The algebraic transformations preserve equality, so the final value of (x) is exactly the unique coordinate satisfying both line equations.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    m1, b1 = map(float, input().split())
    m2, b2 = map(float, input().split())

    x = (b2 - b1) / (m1 - m2)
    print(x)

if __name__ == "__main__":
    solve()

The first input line is parsed into m1 and b1, matching the first equation (y=m_1x+b_1). The second line is parsed in the same way.

The expression (b2 - b1) / (m1 - m2) follows the derived formula directly. Keeping the subtraction order exactly as written matters. Changing the numerator to b1 - b2 without also changing the denominator would negate the answer.

Python's float type is used because the input consists of floating-point values. Python does not have the integer-overflow issue that would arise in fixed-width integer languages, although floating-point arithmetic still has the usual finite-precision behavior. There is no reason to round the coefficients before calculating the intersection, since doing so could be especially harmful when the slopes are close.

There is also no need for a loop because the problem contains exactly one pair of lines rather than multiple test cases. The source problem explicitly describes two input rows and one output value.

Worked Examples

Sample 1

The sample input is

5 3
-6 -20

The initial state is (m_1=5), (b_1=3), (m_2=-6), and (b_2=-20).

Step (m_1) (b_1) (m_2) (b_2) Numerator (b_2-b_1) Denominator (m_1-m_2) (x)
Read input 5 3 -6 -20
Compute differences 5 3 -6 -20 -23 11
Divide 5 3 -6 -20 -23 11 -23/11
Print 5 3 -6 -20 -23 11 -2.090909090909091

The denominator is positive because the first line has the larger slope, while the numerator is negative because the second line has the smaller intercept. Their ratio is negative, correctly placing the intersection to the left of the (y)-axis. This matches the published sample output.

Example 2

Consider

2 0
-1 3

The two equations are (y=2x) and (y=-x+3).

Step (m_1) (b_1) (m_2) (b_2) Numerator (b_2-b_1) Denominator (m_1-m_2) (x)
Read input 2 0 -1 3
Compute differences 2 0 -1 3 3 3
Divide 2 0 -1 3 3 3 1.0
Print 2 0 -1 3 3 3 1.0

At (x=1), the first line gives (y=2), and the second line also gives (y=2). The equality of the two resulting (y)-values confirms that the computed coordinate is the actual intersection.

Complexity Analysis

Measure Complexity Explanation
Time (O(1)) The solution performs a fixed number of arithmetic operations.
Space (O(1)) Only four coefficients and one result are stored.

The input size is constant, so the algorithm is comfortably within the one-second time limit and uses only a negligible amount of the 256 MB memory limit.

Test Cases

The original source provides one sample and does not define multiple test cases. Since the statement also does not provide a numeric maximum bound for the floating-point coefficients, a literal maximum-size test cannot be constructed from the published specification. The custom tests below instead exercise the numerical extremes and structural boundary cases that matter for this formula.

# Helper: run solution on input string, return output string.
import sys
import io

def solve():
    m1, b1 = map(float, input().split())
    m2, b2 = map(float, input().split())

    x = (b2 - b1) / (m1 - m2)
    print(x)

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    solve()
    out = sys.stdout.getvalue()

    sys.stdin = old_stdin
    sys.stdout = old_stdout

    return out

# Provided sample.
assert run("5 3\n-6 -20\n") == "-2.090909090909091\n", "sample 1"

# Minimum-size style case: two simple intersecting lines.
assert run("1 0\n-1 2\n") == "1.0\n", "simple intersection"

# Zero intercepts and positive intersection.
assert run("2 0\n-1 3\n") == "1.0\n", "zero intercept"

# Negative intersection.
assert run("3 5\n1 1\n") == "-2.0\n", "negative x-coordinate"

# Very close slopes, exercising a small denominator.
assert run("1.000001 2\n1 1\n") == "-1000000.0\n", "close slopes"
Test input Expected output What it validates
5 3 / -6 -20 -2.090909090909091 Provided sample and negative result
1 0 / -1 2 1.0 Basic algebra and crossing at a positive coordinate
2 0 / -1 3 1.0 Zero intercept handling
3 5 / 1 1 -2.0 Negative intersection
1.000001 2 / 1 1 -1000000.0 Small denominator and close slopes

The tests compare the exact decimal representation produced by Python for these particular inputs. For a more general testing harness, comparing floating-point values with a tolerance would be preferable because mathematically equal floating-point computations can sometimes differ in their final low-order bits.

Edge Cases

The negative-coordinate case is handled without any special branch. For

5 3
-6 -20

the algorithm computes (b_2-b_1=-23) and (m_1-m_2=11), giving (x=-23/11). The negative numerator naturally produces the correct negative coordinate.

The zero-intercept case is equally direct. For

2 0
-1 3

the numerator is (3-0=3) and the denominator is (2-(-1)=3), so the result is (1). Substituting (x=1) into both equations gives (y=2), confirming the intersection.

The close-slope case demonstrates why the solution should not use a search or aggressively rounded coefficients. With

1.000001 2
1 1

the denominator is only (0.000001). The formula gives

[ x=\frac{1-2}{1.000001-1} =\frac{-1}{0.000001} =-1000000. ]

A coarse numerical search could miss this intersection entirely if its search range were too small, while the direct formula obtains it immediately.

Finally, equal slopes are excluded by the input guarantee. For

2 1
2 5

the denominator would be zero, representing parallel lines. The program does not add a special output for this case because the judge never supplies it. Adding an arbitrary branch could actually obscure the central guarantee of the problem, which is that every input consists of two intersecting lines.