POINPOLY - Editorial

Another approach :

1)Find centroid of Polygon. The polygon centroid must lie inside the polygon as it is convex.

  1. Join each vertex and the polygon centroid, thus forming ‘N’ triangles.

  2. Find centroid for each of ‘N’ triangles. (Centroid of all triangles will also lie inside each respective triangle and obviously the polygon)

  3. Now you have total ‘N+1’ points inside polygon.

  4. Check for each point whether it lies inside polygon. Break after you find floor(N/10) such points.

  5. 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]

1 Like

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.

1 Like

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

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

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?

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

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.

1 Like

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.

3 Likes

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