×

# POINPOLY - Editorial

Author: Praveen Dhinwa
Tester: Hanlin Ren
Editorialist: Hanlin Ren

MEDIUM

# PREREQUISITES:

Convex Polygon, constructive algorithms

# PROBLEM:

Given an $n$-sided convex polygon where all vertices have integral coordinates. Output $\lfloor n/10\rfloor$ distinct integral points strictly inside the polygon.

# QUICK EXPLANATION:

This editorial contains $3$ solutions: (Setter's solution is the easiest among them)

### Setter's solution

• For a polygon of $10$ points, one can easily find one point by checking the midpoints of some chords.
• Let $P_1,P_2,\dots,P_n$ be the vertices.
• For each $k=10i+1$, we find one integral point in the convex hull of $P_k,P_{k+1},\dots,P_{k+9}$.

### A dfs/bfs-based solution

• We need a data structure that given a point, tells in $O(\log n)$ time if the point is strictly in the polygon.
• First, we arbitrarily find one point in the polygon.
• Then we check if its neighbors are in the polygon; check its neighbors' neighbors; and so on.

### Tester's solution

• Let $U(x_0)$ be the intersection of $x=x_0$ with the upper hull. Similarly $L(x_0)$ for lower hull.
• Find (roughly) the smallest $x_0$ such that the open interval $(L(x_0), U(x_0))$ contains some integer.
• Imagine a vertical line at $x=x_0$. Then we can output all integral points on the vertical line.
• We repeatedly increase $x_0$, moving the vertical line rightwards. During this process we can maintain $L(x_0),U(x_0)$ and iterate all integral points in the polygon.

View Content

View Content

View Content

View Content

# ALTERNATIVE SOLUTION:

There are many solutions for this problem. Please, feel free to share your approaches!

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution 1 can be found here.
Tester's solution 2 can be found here.
Tester's solution 3 can be found here.

This question is marked "community wiki".

7★r_64
261617
accept rate: 16%

18.2k347492525

With respect to first solution how do you make sure that all points are unique (that they don't overlap as incase of regular polygon if opposite vertices are chosen they would overlap at center)????

(12 Feb, 15:56) 3★

Is this regarding the setter's solution? Selecting first 10 points and finding one central point and then moving to next 10 and so on?

(12 Feb, 15:59) 0★

@pk1210 - In case its a doubt in general, you can use set to avoid duplicates. If its asking about setter or tester's solution, please specify which one.

(13 Feb, 00:46)

@pk1210: these n/10 points are in different "subpolygon"s, as you can see in the figure. So they have to be different.

(13 Feb, 06:37) 7★

 3 After some pondering I realized that the constraints (convexity and non-collinearity) seems to force that there must exist a lot of internal points (and hence enough points will always exist). I tried a rough solution that I did not expect to work at the time, randomly pick two non-adjacent corner points $A=(x_1,y_1)$ and $B=(x_2,y_2)$ and if $g=\gcd(x_1-x_2,y_1-y_2) \neq 1$ then there exist $g-1$ integer points along line $AB$ which can easily be found. Repeat until enough unique points are found. After getting AC with this the best rationale I can give for this working is that for this not to work you would have to pick a set of points where all pairwise differences in $x$ and $y$ are coprime, which seems quite unlikely for sets with a large number ($\geq10$) of points. answered 13 Feb, 04:23 6★algmyr 73●4 accept rate: 0% You can actually prove that you will always find at least n / 10 points. See the setter's solution described in the editorial for a proof of it. (13 Feb, 12:46) admin ♦♦0★
 2 @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 answered 14 Feb, 13:29 2★zizx 49●4 accept rate: 0% I had the same question. How does 2 points being in the same hole prove that the midpoint is integral ? (14 Feb, 14:49) @zizx @dollarakshay x and y can have 4 scenarios O O E O O E E E now if there are four holes and there are 5 pigeons then as author mentioned that 2 of them will go to the same hole it means that the 2nd one which is going to the same hole will resemble the same property as that of 1st one i.e if O O goes the 2nd again O O will go their sum = E E hence E/2 E/2 will be an integer similarly if O E goes then O E will go to the same hole their sum = E E hence E/2 E/2 will be integer this much i understood (14 Feb, 15:16) Oh now I get it. Basically it says that there can only be 4 kinds of numbers: x-ODD, y-ODD x-ODD, y-EVEN x-EVEN, y-ODD x-EVEN, y-EVEN  So this means that if you have 5 points, 2 of them need to fall into one of these groups. So adding 2 numbers from the same group and dividing by 2 will always be an integer (odd+odd)/2 = Integer (even+even)/2 = Integer  (14 Feb, 15:18) hmm.. right (14 Feb, 15:22)
 1 The entire editorial dosen't even talk about Pick's Theorm, which is required to even check whether or not it is possible to find that many integer points. answered 12 Feb, 16:02 176●1●7 accept rate: 5% shoelace formula too. :P (12 Feb, 16:03) 4 Editorial doesn't talk about it because it is always possible to find n/10 points in any convex polygon of n sides with integral coordinates. It shows you one way of how to find such points. (12 Feb, 16:04) admin ♦♦0★ @admin can u give a proof of it? (12 Feb, 17:45) 1 The setter's solution gives a proof of it. (13 Feb, 12:45) admin ♦♦0★
 1 Another approach : 1)Find centroid of Polygon. The polygon centroid must lie inside the polygon as it is convex. 2) Join each vertex and the polygon centroid, thus forming 'N' triangles. 3) Find centroid for each of 'N' triangles. (Centroid of all triangles will also lie inside each respective triangle and obviously the polygon) 4) Now you have total 'N+1' points inside polygon. 5) Check for each point whether it lies inside polygon. Break after you find floor(N/10) such points. 6) Time complexity = O(n) + O(n*log(n)) = O(nlog(n)). [Note: a) This approach surely works of N>50 I guess. Probably requires some fine tunning for 10<=N<=50. b) Approach fits in time limit probably because the first floor(N/10) points we calculate always lie inside the polygon, so for(N>50) no need even to check whether they lie inside the polygon or not] answered 12 Feb, 16:12 4★aniketmk 11●2 accept rate: 0%
 1 @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. answered 13 Feb, 14:08 280●6 accept rate: 10% Thanks for sharing this :) (13 Feb, 14:20) pk3012★ If we could find if a point is inside a convex polygon in O(logN),couldnt we just run bfs from any vertex without dividing it into triangles? Please @kushal101 if u could say if its possible or not. (15 Feb, 22:00)
 1 Weak Test case Have a look at this solution of Poinpoly problem (it's not mine) https://www.codechef.com/viewsolution/17306405 answered 14 Feb, 09:54 11●1 accept rate: 0% Firstly, the approach is correct- its only taking in mid point which will always lie inside polygon. He cannot get 2 same mid points from same starting/base vertex. He is taking one vertex, finding mid point of all vertices from that, it will give him $N/10$ points then and there. The only edge case where it fails is, where the mid point lies outside due to the loss f decimal/truncation of decimal. Why is it weak test cases? (14 Feb, 10:41) Its weak because even after failing on some edge cases the user is getting 70 points. (14 Feb, 14:26)
 1 @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. answered 15 Feb, 19:05 11●1 accept rate: 0%
 1 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
 0 From the given n points- Form 4 groups like even_even, even_odd, odd_even and odd_odd(where x_y are x and y cordinates respectively). Find the mid points of of all elements in a group. They will have integer cordinates and will be inside the polygon. answered 12 Feb, 17:39 1 accept rate: 0%
 0 I did this problem by finding the centroid of the polygon. Since the polygon is Convex, Centroid is surely strictly inside the polygon.Then find the mid pts of each of the N vertices and the centroid and stop when the number of points exceed floor(n/10). This gave me 70 pts....probably some careful implementation was required for low N. For small N I did horizontol scanline. (Drawing horizontol lines and checking the intersection points). answered 12 Feb, 18:06 5★abx_2109 275●1●11 accept rate: 0% True, low $N$ seemed to give nightmares. Passing 70 point task was easier than the 30 mark one. Had to at last swallow pride and resort to brute force for low $N$ (13 Feb, 01:35) Yeah. I am very much interested in knowing that N=10 testcase in the first subtask which failed almost all the random techniques. Can @admin share that testcase? (14 Feb, 14:36) abx_21095★ I talked to @admin regarding that. I dont think it will help much, since the polygons in that TC arent "small". Example, one of the cases where many solutions failed was- 10 -479724248 168812047 -479723521 168812070 -479723209 168812080 -479721714 168812128 -479720573 168812165 -479718272 168812240 -479717385 168812269 -479716591 168812295 -479715554 168812329 -479714732 168812356 Basic idea is, huge change in x axis with very small change in y axis. Your code passed this TC though, but quite many failed at it (esp those who took mid points) (16 Feb, 14:29)
 0 since we only have to find n/10 points we can iterate over all given points of the polygon and look for the point in the immediate neighbour i.e(left, right, up, down) and add them to the set. the point checking part could be done with area of triangle approach where area of all 3 subtriangle == area of main triangle(3 consecutive points of the polygon). answered 12 Feb, 18:14 51●2 accept rate: 0%
 0 I followed the tester's approach by scanning a line from left to right. I found the intersection points by maintaining a list of lower and upper parts of polygon and calculating intersection points from the equation of a line. I got 70 points and couldn't pass the first test case in first subtask. Here is a link to my solution. Can anybody point out to me which test case I am missing? answered 13 Feb, 00:35 4★gomu 146●4 accept rate: 7% 2 The basic idea of this case was including a point which is outside in the answer .I cant help much, except for this TC had points close by, steep sides and $T=100$, and $N=10$ for atleast 1 case. (13 Feb, 01:54)
 0 I used the bfs approach, but to check the point is inside or outside, I used a different approach, I basically triangulated the polygon and in each triangle I used the bfs approach to find the points. Checking if a point lies inside a triangle or not takes O(1). answered 13 Feb, 01:33 164●5 accept rate: 12%
 0 My approach was very different and very easy too. We just use one property of a polygon: If A and B are distinct vertices, then every point on segment AB will be inside it. There are N vertices. We can divide them into 4 disjoint groups based on the parities of X and Y coordinates. (first group: all vertices (x,y) where x is odd and y is odd etc.) It's clear that inside each group, if we take any 2 points A and B, the midpoint of segment AB will have integer coordinates, since both X and Y coordinates have same parities. There are 4 groups, so the largest group will have at least [N/4] points. We can simply choose one vertex and connect it to every other in this group, giving us [N/4] - 1 distinct points, which is more than [N/10] already. answered 13 Feb, 01:52 4★llaki10 1●1 accept rate: 0%
 0 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 answered 13 Feb, 06:25 63●6 accept rate: 0%
 0 @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 ?? answered 13 Feb, 09:08 4★ranadev 0 accept rate: 0% No points may coincidence but fortunately non of first n/10 points u found coincided.may be test cases are weak. (15 Feb, 07:13)
 0 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. answered 13 Feb, 09:37 1●1 accept rate: 0%
 0 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 answered 13 Feb, 09:50 3★dbarman 1●1 accept rate: 0%
 0 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 answered 13 Feb, 11:09 118●6 accept rate: 0% Say that the lower y coord is 2.3 , and upper y coord is 2.8. What will your algo do here? Keep in mind that you can intersect the edge at non integral points. Omitting the decimal may cause point to lie out of polygon. (13 Feb, 12:52) for that i have used if(lower_y>higher_y) continue; isn't that sufficient , as it will skip this case and continue further (13 Feb, 13:36)
 0 I used line sweeping algorithm to print the points. Link to my solution is as follow: https://www.codechef.com/viewsolution/17365491 answered 13 Feb, 15:48 2 accept rate: 0% can u explain me what u exactly did as i tried almost the same thing but it was WA. 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. (13 Feb, 16:07) you need to count from floor(lower_y+1.0) to ceil(higher-1.0) (13 Feb, 17:48)
 0 i have tried both approach dividing into triangles and simply using whole polygon: 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 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 ** answered 13 Feb, 16:05 3★abhi55 11●2 accept rate: 0%
 0 Here, in the convex polygon, all interior angles are less than or equal to 180 degrees, OR strictly less than 180 degrees. answered 13 Feb, 17:31 1 accept rate: 0% From the question: No three vertices are collinear. (13 Feb, 18:25)
 0 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 answered 14 Feb, 14:26 4 accept rate: 0% @pavitra_ag (agni) just make a small change for(long long int j=i+1;j<=i+8;j++) (14 Feb, 15:00) you should not start j from i as it will be a[0]+a[0]/2 in the very first scenario resulting wrong answer ... (14 Feb, 15:02) can you please explain to me why doing j=i+1 works? All I was doing was to pick 10 points then next 10 points and so on. If I start from j=i+1 I never pick the first point. A little help :) (15 Feb, 22:37)
 0 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. answered 15 Feb, 18:18 11●1 accept rate: 0% Minor point: you don't handle the case where two mid points are identical. Input  1 25 75 21 66 21 55 20 45 18 36 16 28 14 21 12 15 10 10 8 6 6 3 4 1 2 0 0 1 -2 3 -4 6 -6 10 -8 15 -10 21 -12 28 -14 36 -16 45 -18 55 -20 65 -21 74 -21  gives output  70 0 70 0  (2 days ago)
 0 @souradeep1999 can u please explain ur approach ! answered 15 Feb, 18:30 2★zizx 49●4 accept rate: 0%
 0 @souradeep1999 that was a good approach u r choosing everytime pure integers . with no loss of precision thanks for the explanation answered 15 Feb, 21:19 2★zizx 49●4 accept rate: 0%
 0 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- (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. answered 16 Feb, 15:10 12.1k●1●3●19 accept rate: 18%
 0 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 answered 16 Feb, 18:14 4★monsij 53●5 accept rate: 0% 1 But your basic reasoning is not correct. We can create a square, which is convex, with corners at $(\pm 1, \pm 1)$. The only internal integer point is at $(0,0)$, but doesn't have the form $(x \pm 1, y)$ or $(x, y \pm 1)$. A more general counter-example follows from multiplying the points in the sample data by some matrix like $\left( \begin{matrix} 1000 & 999999 \\ 1 & 1000 \end{matrix}\right)$. The result is a long narrow convex polygon. The internal integer points are not close to the vertices. (17 Feb, 01:57) if (x-1,y-1) and (x+1,y+1) i think all the cases should come under it (17 Feb, 02:45) 1 Consider a convex quadrilateral with corners $(0,0)$, $(2,0)$, $(1002,2)$, and $(1000,2)$. The only internal grid point is $(501,1)$. Or a more complicated case:  1 11 0 0 1000999 1001 3001997 3002 5001995 5002 9999990 10000 9997990 9998 8994991 8995 6991993 6992 3991996 3992 993999 994 -2000 -2  which has 71 internal grid points. The first few are  994999 995 995999 996 996999 997 997999 998 998999 999 ..  but they are not close to the vertices. (2 days ago) yes.. right !! (2 days ago) Wow! How did you derive this @john_smith_3 ? Any tips on how to generate such sexy polygons? :3 (2 days ago) 2 Take the co-ordinates of the original sample data, and multiply by an integer 2 by 2 matrix with determinate 1. $$\left( \begin{matrix} 1000 & 999999 \\\\ 1 & 1000 \end{matrix} \right) \left( \begin{matrix} 0 & 1 & 2 & 2 & 0 & -2 & -5 & -8 & -8 & -6 & -2 \\\\ 0 & 1 & 3 & 5 & 10 & 10 & 9 & 7 & 4 & 1 & 0 \end{matrix} \right)$$ 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. (2 days ago) Wow!! Thats so nice to know!! Thank you @john_smith_3 !! (2 days ago) @john_smith_3 very clever trick !! #@ (2 days ago) 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. (2 days ago) @john_smith_3 :IF we consider a square,we require [4/10] = 0 points.So not an issue! (2 days ago) monsij4★ @monsij - he gave another example of convex polygon where internal points were quite far from vertices. (2 days ago) showing 5 of 11 show all
 0 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. answered 2 days ago 81●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×13,321
×2,112
×221
×126
×60
×32