### Usu's blog

By Usu, history, 5 years ago,

Hey! Can anybody help with this problem? This problem says that we are in a point (x,y) and we have n lines (defined by the line's equation a,b,c). How many lines can we see from that point? If we see only a point of a line, we do not consider that line at all. I think we should find the intersections of all the lines firstly, but I do not have certain ideas. The number of lines is 10.000, does anybody have ideas?

• +3

 » 5 years ago, # |   +5 Link to the problem?Regarding the solution, this problem can be reduced to a half plane intersection problem, you just need to know for each line, which half plane it “keeps”, and the answer is the halfplane that contains the point.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I don't have a link. I just discussed this with a friend who saw it in a printed book. Can you detail more the solution?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +5 Well the reduction to a half plane intersection is somewhat straightforward. If you dont know how to do halfplane intersection you should google it, but I will give a brief explanation to how I do it. You sort the half planes (that are defined by lines) by angle and iterate over them and check if the intersection of halfplanes i and i+2 are a subset of halfplane i+1. If so, you erase halfplane i+1.