This is another way to do it. It allows you to enumerate as many points as you want in O(k+n.log(M)) operations, where k is the number of points returned, and M is the maximum size of any integer coordinate.
First split the polygon into n-2 triangles (emanating from a fixed vertex).
Then for each triangle with vertices (p0, p1, p2), translate to (0, p1-p0, p2-p0), then transform
these vertices by a 2x2 matrix with integer entries and determinant 1 into the form
((0,0), (g,0), (a,b)), where b, g >0. (Could also insist 0ā¤a<g, but it doesnāt matter.)
This is OK to do, because such matrices preserve the integer grid of points. This step takes O(log(M)) operations for each of the n-2 triangles.
Then you can show that the only case there are no interior points is when (g=1 or b=1 or g=b=2) and (b|a or b|(a-g)), which is an O(1) check. You can also show that if there are some interior points then there are least b/4-1/2 of them, which means you can check each of the b horizontal lines inside the triangle and spend no more work than O(#points returned).
(You have to make a slight adjustment for counting points on the edges of the triangles, which
is allowed if they are interior to the polygon.)
If the original points form a convex polygon, then so do the transformed points. Internal grid points of the original polygon will transform 1-to-1 onto the internal grid points of the transformed polygon.
See also the comment by @alexthelemon. There he takes a possibly long thin triangle and transforms it to a nicer shape where it is easy to find the internal grid points.
Hello Everyone!
The approaches used by other participants is really good and clever even at some points. However, amidst all those smart approaches, Iād like to present the approach used by me(I donāt exactly know if it has been mentioned already because of a hefty amount of comments).So, it goes like this, Just select two random or linear non-consecutive points from the given set of points and draw a straight line between them. Count all Integral points on that line excluding the End points (Counting the integral points on a line is left as a healthy exercise for the reader) and store them in a set to avoid duplicates. An extra [log N] is just used in the set operation which too could have been avoided by choosing the the endpoints more smartly. Repeat the approach for two different pair of points to suffice for the N/10 points. I hope it helps. Please feel free to enquire more.
I like this problemā¦ maybe it have short and fast way ā¦ but i solved this in a very very interesting way!
ā¦first i earn 4 chain for this: left , top , right , bottom --> each chain consist from some segment(sequence points): for each point now i must do this; for example for chain in left i must find segment that maybe! intersected with horizontal line passing from our pointā¦ now i just need checked this really intersect or no! if no --> so point is outside polygonā¦ if for all chains we have intersected in 4 case(if in each case exist segment and one case i mentioned(left)) we can say this point is inside polygon ā¦ so now i used bfs from all given points(move in 4 direction and if it was outside i break this else counted and i continue next moving from this) for polygon and check above for each point and save visited point in a set to not visited more than once until we do this for all point on polygon or get ans([N/10] inside).