POINPOLY - Editorial

centroid must lie inside the triangle;

  • c=((x1+x2+x3/3),(y1+y2+y3)/3)
  • (x,y) is congruent to (0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2) mod 3
  • so in this only few combinations will have ( c=((x1+x2+x3),(y1+y2+y3))) congruent (0,0) mod 3
  • for the above combinations c=((x1+x2+x3/3),(y1+y2+y3)/3) is integer always;
  • and by php(pigeon hole principle) we know that atleast X=floor(n/9) will have modulo 3,so we can find (X)C3 centroids which are integers;
  • but this might not always give floor(n/10) points due to some centroids might overlap
  • so we are finding all centroids which are integers if it crosses floor(n/10) we stop
  • we use a set too avoid repetition.
  • time complextity is O(nlogn)
  • view my soln here- https://www.codechef.com/viewsolution/17348337

@lokesh2002
Even I did follow a similar approach First I chose 3 points from the polygon and checked if the centroid of the triangle (Since It always lies inside the polygon) has integer coordinates but I did not check the condition “if my centroids obtained of two different triangles will coincide or not”. My code seems to pass even without checking this condition . So, Is it like two centroids of two different triangles in a convex polygon never coincide (or) any specific reason ??

My code - https://www.codechef.com/viewsolution/17364307

I took a random triangle and used binary search to find the smallest triangle in which the point lies. Then i checked if the point lies inside the triangle by finding the areas of the three trianglesand the entire triangle.
Also i didnt check for all the vertices. Checking the adjacent point of each vertex will suffice.
Complexity -O(nlogn) as we only need to check the 4 adjacent points of each vertex of the polygon.

I just checked the 2 adjacent points of each vertex. Yikessss!!
Checked whether inside by checking if that point lies on the left of 2 edges meeting at that vertex

@r_64 @vijju123

what i did was find the leftmost x and rightmost x

loop through i = lx+1 to rx-1

then for each i , find where the vertical line intersects lower_y coordinate and upper_y coordinate.

then from floor(lower_y)+1 to ceil(higher_y)-1 store all the

values until it reaches our desired result.

is this method wrong ??

https://www.codechef.com/viewsolution/17432565

@admin I think there could have been a better question,by giving the required no of points as input itself, rather than setting it to (n/10). The solution for (n/10) is pretty simpler . But then a case could have been asked for
to print all the points inside the polygon. My approach would handle such cases as well.
I divided the n sided polygon into (n-2) triangles. Now for each triangle, starting from its centroid I ran a bfs to cover all points lying inside it. If there are k points, Complexity is O(klog(k)) since I used set to avoid duplicates.

My code : https://www.codechef.com/viewsolution/17322525 In this code, set the req variable to as desired, to get that many points as output.

1 Like

I used line sweeping algorithm to print the points. Link to my solution is as follow:
https://www.codechef.com/viewsolution/17365491

i have tried both approach dividing into triangles and simply using whole polygon:

  1. Approach 1:simply using polygon

in simply using whole polygon approach first i checked it contain sufficient point or not by using pick’s theorem then calculated maxY and minY and then start sweeping line to adjacent point on boundary of polygon and calculating all points on line by using bresenham line points generating algorithm and checking inclusion also…by this i passed top 6 subcases passed in less time limit and got TLE for last 2.link text

  1. Approach 2:dividing whole polygon into triangle

as said in editorial i divided polygon into triangle and used triangle inclusion test not that Area test for inclusion given in editorial because i feel it will give answer true(for inside) when point is in boundary which will give wrong answer.and similarly find points inside triangle as in previous approach(rotating line point to next point)…but this give large TLE on face only top 2 test case passed.and after testing time taken by traingle inclusion i found out it is taking too much time than fast polygon inclusion test.link text

**After contest over i saw some solutions and find that this question did a comedy with me. it is not a medium problem as tags are saying(binary search…etc.) and can be bypassed easily with some observations.link text
**

Here, in the convex polygon, all interior angles are less than or equal to 180 degrees, OR strictly less than 180 degrees.

Weak Test case Have a look at this solution of Poinpoly problem (it’s not mine) CodeChef: Practical coding for everyone

1 Like

@admin how the pigeonhole principle is working here ? how it can be proved that there will be some midpoint whose x and y are integers . can u clarify it a bit more as i can’t relate pgh principle to midpoint here

2 Likes

I am trying to follow the setter’s logic , but only few subtasks are passing.
Can someone please review my submission and help me.
My code is solution

I see everyone considered it as MEDIUM level Question,but i don’t think so.Though my approach is a bit similar with setter’s solution,but i just use IF ELSE and FOR LOOP only,so for a beginner one can easily deals with it,rather than left it by thinking the vector approach or other algorithm’s

https://www.codechef.com/viewsolution/17430200
Please see my solution and respond if any query,thanking you.

@souradeep1999 can u please explain ur approach !

@zizx
lets see that i am taking n*(n-3)/2 diagonal of the polygon.Then if (x1+x2)=even and (y1+y2)=even at the same time then you will find the perfect mid loint of that diagonal in the form of integer.
If you take any two vertex and find their mid point in form of integer by negletting the decimal points or floating poing there will be some case where error will occur.

1 Like

@souradeep1999 that was a good approach u r choosing everytime pure integers . with no loss of precision

thanks for the explanation

For those who used mid point trick for their answers, the corner cases were like-

10
-479724248 168812047
-479723521 168812070
-479723209 168812080
-479721714 168812128
-479720573 168812165
-479718272 168812240
-479717385 168812269
-479716591 168812295
-479715554 168812329
-479714732 168812356

A simple figure illustration will be like-

![alt text][1]

(PS: Not an art student, cant draw a perfect decagon like that XD)

The crux of these tests is, big change of x (or y) co-ordinate, and very minor/very small change in the y (or x) co-ordinate. Due to this, when calculating midpoint, a +-1 error in y co-oord results in WA (meaning, the decimal part is the deciding factor).

If you truncate the decimal, you fail in the first (upper figure), if you round up the decimal, you fail in the lower one.
[1]: https://discuss.codechef.com/upfiles/Presentation1.jpg

Just keep it simple.
After getting the idea how to check whether a given point is inside the given polygon or not,I adopted the following strategy.
Since it is a convex polygon ,say for a vertex (x,y) it is guaranteed that one of (x,y-1),(x,y+1),(x-1,y),(x+1,y) will definitely lie inside the polygon.So just iterate through all given n points and break out when you get [n/10] points.
My solution : My-Solution-POINPOLY

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.)

1 Like

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.