Im my opinion you should just draw random lines following a normal distribution and then check. If I did my calculations right that should have an O(n^-1) complexity.

you are welcome