Determine if a set of lines lie in one side of a point and another set of lines lie in the other side

Given two set A and B of lines with n lines in total and a poin开发者_如何转开发t p. How do u determine if A lines lie in one side of p and B lines lie in the other side?

Unless all of the lines are mutually parallel, they'll always cross both sides of p, since they go on forever. Otherwise, draw a line parallel to one of the other lines that passes through p, and this line will divide the two sets.

Assuming the following:
1. This is not homework.
2. "Cross P" means that, for a given x,y range they don't cross. If we're talking about the entire axis, then the lines in A and B must be parallel with respect to their set and this question becomes trivial.

Then the simple (albeit naive) approach (O(n)) is to simply compare each x value of the lines to the x value of the point (for your given y-value of p). If, for the given y, all the x-coordinates of the set A (or B) are to the left of the given point and for the given x all the y values are NOT above this point, then that set is on one side. Run the same test for the other set and if all the lines are on the other side. Et viola. :)

Hope this helps.