I have checked all the posts and found there are two ways to represent a line:
- ax + by = c, which can cover all cases but requires a gcd
function for normalization.
- 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...
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.