Which line representation is better?

  • 2

    I have checked all the posts and found there are two ways to represent a line:

    1. ax + by = c, which can cover all cases but requires a gcd
      function for normalization.
    2. y = kx + d, which is simple but cannot cover the lines parallel to x-axis.

    I think it is hard to say which is better. However, I prefer the latter...Anybody knows a better way?

    In my submission code, I take the dynamic programming idea and use the y=kx+d representation. Due to the divide-and-conquer, we only need the slope k (d is not necessary any more) as the unique key for each line. This approach is much clear and only one value as hash key. The time complexity is still O(n^2) but the average time cost should be better.

    You can also review my code in my blog: http://www.cnblogs.com/zzzdevil/p/3513294.html

    It is a blog hosting in Chinese, but the post is in English...

    Sorry for the ugly English...

  • 0

    You can only consider the slopes and still get the correct answer. I used Java so I used Double.POSTIVIE_INFINITY to represent vertical lines.

  • 1

    extend representation of lines and points are better.
    lines are represented as (a, b, c)
    and points are represented as (x, y, 1)
    then, operations of dot product and outer product are enough to solve this problem.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.