@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 ??
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
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 ??
The setter’s solution gives a proof of it.
1 Like
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.
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.
for that i have used
if(lower_y>higher_y) continue;
isn’t that sufficient , as it will skip this case and continue further
@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
Thanks for sharing this 
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:
- 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
**
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.
Here, in the convex polygon, all interior angles are less than or equal to 180 degrees, OR strictly less than 180 degrees.
you need to count from floor(lower_y+1.0) to ceil(higher-1.0)
From the question: No three vertices are collinear.
Weak Test case Have a look at this solution of Poinpoly problem (it’s not mine) https://www.codechef.com/viewsolution/17306405
1 Like
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?
@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