Given array of line segments (line between two points). Find can a line (infinite length) be drawn from origin(0,0) which does not intersect any of these lines segements.
line: p1(x1,y1) to p2(x2,y2)
Return type: True or False
Follow up:
Find if a line can be drawn passing through point (x,y) without intersecting any other line segments.
I solved it in O(n*logn) time complexcity with some help from interviewer.
Problem boils down to finding gaps in a list of pairs.
Algo:
- Find angle formed by line with origin. [Interviewer mentioned that I can assume few mathematical functions if needed]. (Returns value of angle in radian)
- Convert array of line segments to array of angles(list of startAngle, endAngle).
- For case when line passes through one gap but doesn't pass from other side, he suggested we can add complement of each angle into array as well. [Complement of sector(angle1, angle2) will be sector((angle1+pi)%pi, (angle2+pe)%pi)]
- Check can we find a gap between two segment in the angles array.
Follow up soln:
Move origin to point given. (Shifiting origin)
Comments (10)