POINPOLY - Editorial

editorial
, , , , ,
55

@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

56

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
57

hmm… right

58

No points may coincidence but fortunately non of first n/10 points u found coincided.may be test cases are weak.

59

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.

60

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 :slight_smile:

61

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)

62

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.

1 Like
63

if (x-1,y-1) and (x+1,y+1) i think all the cases should come under it

64

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.

1 Like
65

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
66

yes… right !!

67

Wow! How did you derive this @john_smith_3 ? Any tips on how to generate such sexy polygons? :3

68

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.

3 Likes
69

Wow!! Thats so nice to know!! Thank you @john_smith_3 !!

70

@john_smith_3 very clever trick !! #@

71

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.

72

@john_smith_3 :IF we consider a square,we require [4/10] = 0 points.So not an issue!

73

@monsij - he gave another example of convex polygon where internal points were quite far from vertices.

74

One of the best editorials I have ever seen, this is amazing stuff.