POINPOLY - Editorial

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

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

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

1 Like

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?

shoelace formula too. :stuck_out_tongue:

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.

4 Likes

@admin can u give a proof of it?

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

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

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.

2 Likes

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