POINPOLY - Editorial

editorial
, , , , ,
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.