Problem

Given two lines on a Cartesian plane, determine whether they intersect. Each line is represented in the form $ax + by + c = 0$.

Examples

Example 1

1
2
3
4
5
6
7

Input:
  Line 1: 2x + 3y + 4 = 0
  Line 2: 4x + 6y + 8 = 0
Output:
  True
Explanation:
  The lines are the same (they overlap), so they intersect everywhere.

Example 2

1
2
3
4
5
6
7

Input:
  Line 1: x + y + 1 = 0
  Line 2: x + y - 2 = 0
Output:
  True
Explanation:
  The lines are parallel but have different intercepts, so they do not overlap, but they are not the same line. They do not intersect.

Example 3

1
2
3
4
5
6
7

Input:
  Line 1: x + y + 1 = 0
  Line 2: x - y + 2 = 0
Output:
  True
Explanation:
  The lines have different slopes, so they intersect at a single point.

Constraints

  • Each line is represented by coefficients $(a, b, c)$, all real numbers.
  • Lines may be identical, parallel, or intersecting.

Solution

Method 1 – Slope Comparison

Intuition

Two lines on a Cartesian plane will intersect unless they are parallel and not coincident. The slope of a line $ax + by + c = 0$ is $-a/b$ (if $b \neq 0$). If the slopes are different, the lines intersect. If the slopes are the same, check if the lines are coincident (identical) or parallel (never meet).

Approach

  1. For each line, extract coefficients $(a, b, c)$.
  2. Compute the slope for each line as $-a/b$ (handle vertical lines where $b = 0$).
  3. If slopes differ, lines intersect at a single point.
  4. If slopes are the same:
    • If the lines are coincident (all coefficients proportional), they overlap (infinite intersection).
    • Otherwise, they are parallel and do not intersect.
  5. Use a small epsilon for floating point comparison.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
 public:
  static constexpr double kEpsilon = 1e-9;
  bool Intersect(const std::array<double, 3>& l1, const std::array<double, 3>& l2) {
    double a1 = l1[0], b1 = l1[1], c1 = l1[2];
    double a2 = l2[0], b2 = l2[1], c2 = l2[2];
    // Handle vertical lines
    if (std::abs(b1) < kEpsilon && std::abs(b2) < kEpsilon) {
      return std::abs(a1 * c2 - a2 * c1) < kEpsilon;
    }
    double slope1 = (std::abs(b1) < kEpsilon) ? std::numeric_limits<double>::infinity() : -a1 / b1;
    double slope2 = (std::abs(b2) < kEpsilon) ? std::numeric_limits<double>::infinity() : -a2 / b2;
    if (std::abs(slope1 - slope2) > kEpsilon) return true;
    // Check if lines are coincident
    double ratio_a = (std::abs(a2) > kEpsilon) ? a1 / a2 : 0;
    double ratio_b = (std::abs(b2) > kEpsilon) ? b1 / b2 : 0;
    double ratio_c = (std::abs(c2) > kEpsilon) ? c1 / c2 : 0;
    return std::abs(ratio_a - ratio_b) < kEpsilon && std::abs(ratio_b - ratio_c) < kEpsilon;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

const epsilon = 1e-9
func Intersect(l1, l2 [3]float64) bool {
    a1, b1, c1 := l1[0], l1[1], l1[2]
    a2, b2, c2 := l2[0], l2[1], l2[2]
    if math.Abs(b1) < epsilon && math.Abs(b2) < epsilon {
        return math.Abs(a1*c2 - a2*c1) < epsilon
    }
    var slope1, slope2 float64
    if math.Abs(b1) < epsilon {
        slope1 = math.Inf(1)
    } else {
        slope1 = -a1 / b1
    }
    if math.Abs(b2) < epsilon {
        slope2 = math.Inf(1)
    } else {
        slope2 = -a2 / b2
    }
    if math.Abs(slope1-slope2) > epsilon {
        return true
    }
    var ratioA, ratioB, ratioC float64
    if math.Abs(a2) > epsilon {
        ratioA = a1 / a2
    }
    if math.Abs(b2) > epsilon {
        ratioB = b1 / b2
    }
    if math.Abs(c2) > epsilon {
        ratioC = c1 / c2
    }
    return math.Abs(ratioA-ratioB) < epsilon && math.Abs(ratioB-ratioC) < epsilon
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class Solution {
  private static final double EPSILON = 1e-9;
  public boolean intersect(double[] l1, double[] l2) {
    double a1 = l1[0], b1 = l1[1], c1 = l1[2];
    double a2 = l2[0], b2 = l2[1], c2 = l2[2];
    if (Math.abs(b1) < EPSILON && Math.abs(b2) < EPSILON) {
      return Math.abs(a1 * c2 - a2 * c1) < EPSILON;
    }
    double slope1 = Math.abs(b1) < EPSILON ? Double.POSITIVE_INFINITY : -a1 / b1;
    double slope2 = Math.abs(b2) < EPSILON ? Double.POSITIVE_INFINITY : -a2 / b2;
    if (Math.abs(slope1 - slope2) > EPSILON) return true;
    double ratioA = Math.abs(a2) > EPSILON ? a1 / a2 : 0;
    double ratioB = Math.abs(b2) > EPSILON ? b1 / b2 : 0;
    double ratioC = Math.abs(c2) > EPSILON ? c1 / c2 : 0;
    return Math.abs(ratioA - ratioB) < EPSILON && Math.abs(ratioB - ratioC) < EPSILON;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
  private val epsilon = 1e-9
  fun intersect(l1: DoubleArray, l2: DoubleArray): Boolean {
    val (a1, b1, c1) = l1
    val (a2, b2, c2) = l2
    if (Math.abs(b1) < epsilon && Math.abs(b2) < epsilon) {
      return Math.abs(a1 * c2 - a2 * c1) < epsilon
    }
    val slope1 = if (Math.abs(b1) < epsilon) Double.POSITIVE_INFINITY else -a1 / b1
    val slope2 = if (Math.abs(b2) < epsilon) Double.POSITIVE_INFINITY else -a2 / b2
    if (Math.abs(slope1 - slope2) > epsilon) return true
    val ratioA = if (Math.abs(a2) > epsilon) a1 / a2 else 0.0
    val ratioB = if (Math.abs(b2) > epsilon) b1 / b2 else 0.0
    val ratioC = if (Math.abs(c2) > epsilon) c1 / c2 else 0.0
    return Math.abs(ratioA - ratioB) < epsilon && Math.abs(ratioB - ratioC) < epsilon
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from typing import List

class Solution:
    def intersect(self, l1: List[float], l2: List[float]) -> bool:
        epsilon = 1e-9
        a1, b1, c1 = l1
        a2, b2, c2 = l2
        if abs(b1) < epsilon and abs(b2) < epsilon:
            return abs(a1 * c2 - a2 * c1) < epsilon
        slope1 = float('inf') if abs(b1) < epsilon else -a1 / b1
        slope2 = float('inf') if abs(b2) < epsilon else -a2 / b2
        if abs(slope1 - slope2) > epsilon:
            return True
        ratio_a = a1 / a2 if abs(a2) > epsilon else 0.0
        ratio_b = b1 / b2 if abs(b2) > epsilon else 0.0
        ratio_c = c1 / c2 if abs(c2) > epsilon else 0.0
        return abs(ratio_a - ratio_b) < epsilon and abs(ratio_b - ratio_c) < epsilon
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn intersect(l1: [f64; 3], l2: [f64; 3]) -> bool {
        let epsilon = 1e-9;
        let (a1, b1, c1) = (l1[0], l1[1], l1[2]);
        let (a2, b2, c2) = (l2[0], l2[1], l2[2]);
        if b1.abs() < epsilon && b2.abs() < epsilon {
            return (a1 * c2 - a2 * c1).abs() < epsilon;
        }
        let slope1 = if b1.abs() < epsilon { f64::INFINITY } else { -a1 / b1 };
        let slope2 = if b2.abs() < epsilon { f64::INFINITY } else { -a2 / b2 };
        if (slope1 - slope2).abs() > epsilon {
            return true;
        }
        let ratio_a = if a2.abs() > epsilon { a1 / a2 } else { 0.0 };
        let ratio_b = if b2.abs() > epsilon { b1 / b2 } else { 0.0 };
        let ratio_c = if c2.abs() > epsilon { c1 / c2 } else { 0.0 };
        (ratio_a - ratio_b).abs() < epsilon && (ratio_b - ratio_c).abs() < epsilon
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    intersect(l1: [number, number, number], l2: [number, number, number]): boolean {
        const epsilon = 1e-9;
        const [a1, b1, c1] = l1;
        const [a2, b2, c2] = l2;
        if (Math.abs(b1) < epsilon && Math.abs(b2) < epsilon) {
            return Math.abs(a1 * c2 - a2 * c1) < epsilon;
        }
        const slope1 = Math.abs(b1) < epsilon ? Infinity : -a1 / b1;
        const slope2 = Math.abs(b2) < epsilon ? Infinity : -a2 / b2;
        if (Math.abs(slope1 - slope2) > epsilon) return true;
        const ratioA = Math.abs(a2) > epsilon ? a1 / a2 : 0;
        const ratioB = Math.abs(b2) > epsilon ? b1 / b2 : 0;
        const ratioC = Math.abs(c2) > epsilon ? c1 / c2 : 0;
        return Math.abs(ratioA - ratioB) < epsilon && Math.abs(ratioB - ratioC) < epsilon;
    }
}

Complexity

  • ⏰ Time complexity: O(1), since all operations are simple arithmetic and comparisons.
  • 🧺 Space complexity: O(1), only a constant number of variables are used.