You are given a convex polygon consisting of N points on its boundary (consecutive & counter-clock-wise order) and a set of M points on the plane. Check if those M points lie inside the given convex polygon. What is the time & space complexity?
3 <= N, M <= 10000

Example:
polygon: [ [0,0], [2,0], [2,2], [0,2] ]
points: [ [1,1], [0,2], [1,0], [3,3] ]
output = [ true, true, true, false ]

Note: O(NM) solution is obvious. Can you do it better?

ps: I will post the solution in a few days.