# POINPOLY - Editorial

**URL:** <https://discuss.codechef.com/t/poinpoly-editorial/17995>\
**Category:** editorial\
**Tags:** constructive, convex-polygon, editorial, feb18, medium, poinpoly\
**Created:** [February 3, 2018, 7:29pm UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995 "2018-02-03T19:29:28Z")\
**Posts on this page:** 14\
**Page:** 4

<div class="post-metadata">

**Author:** ![vijju123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/vijju123/32/195207_2.png) [@vijju123](https://discuss.codechef.com/u/vijju123)\
**Post date:** [February 16, 2018, 2:29pm UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/61 "2018-02-16T14:29:31Z")

</div>

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-

```auto
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)

---

<div class="post-metadata">

**Author:** ![john\_smith\_3](https://discuss.codechef.com/user_avatar/discuss.codechef.com/john_smith_3/32/208155_2.png) [@john\_smith\_3](https://discuss.codechef.com/u/john_smith_3)\
**Post date:** [February 17, 2018, 1:57am UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/62 "2018-02-17T01:57:10Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![worldunique](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@worldunique](https://discuss.codechef.com/u/worldunique)\
**Post date:** [February 17, 2018, 2:45am UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/63 "2018-02-17T02:45:36Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![john\_smith\_3](https://discuss.codechef.com/user_avatar/discuss.codechef.com/john_smith_3/32/208155_2.png) [@john\_smith\_3](https://discuss.codechef.com/u/john_smith_3)\
**Post date:** [February 17, 2018, 3:59am UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/64 "2018-02-17T03:59:29Z")

</div>

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:

```auto

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

```auto

994999 995
995999 996
996999 997
997999 998
998999 999
..

```

but they are not close to the vertices.

---

<div class="post-metadata">

**Author:** ![john\_smith\_3](https://discuss.codechef.com/user_avatar/discuss.codechef.com/john_smith_3/32/208155_2.png) [@john\_smith\_3](https://discuss.codechef.com/u/john_smith_3)\
**Post date:** [February 17, 2018, 4:48am UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/65 "2018-02-17T04:48:26Z")

</div>

Minor point: you don’t handle the case where two mid points are identical.

Input

```auto

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

```auto

70 0
70 0

```

---

<div class="post-metadata">

**Author:** ![worldunique](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@worldunique](https://discuss.codechef.com/u/worldunique)\
**Post date:** [February 17, 2018, 6:18am UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/66 "2018-02-17T06:18:18Z")

</div>

yes… right !!

---

<div class="post-metadata">

**Author:** ![vijju123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/vijju123/32/195207_2.png) [@vijju123](https://discuss.codechef.com/u/vijju123)\
**Post date:** [February 17, 2018, 10:42am UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/67 "2018-02-17T10:42:22Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![john\_smith\_3](https://discuss.codechef.com/user_avatar/discuss.codechef.com/john_smith_3/32/208155_2.png) [@john\_smith\_3](https://discuss.codechef.com/u/john_smith_3)\
**Post date:** [February 17, 2018, 3:20pm UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/68 "2018-02-17T15:20:46Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![vijju123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/vijju123/32/195207_2.png) [@vijju123](https://discuss.codechef.com/u/vijju123)\
**Post date:** [February 17, 2018, 5:03pm UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/69 "2018-02-17T17:03:30Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![worldunique](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@worldunique](https://discuss.codechef.com/u/worldunique)\
**Post date:** [February 17, 2018, 5:45pm UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/70 "2018-02-17T17:45:26Z")

</div>

@john_smith_3 very clever trick !! #@

---

<div class="post-metadata">

**Author:** ![john\_smith\_3](https://discuss.codechef.com/user_avatar/discuss.codechef.com/john_smith_3/32/208155_2.png) [@john\_smith\_3](https://discuss.codechef.com/u/john_smith_3)\
**Post date:** [February 17, 2018, 7:06pm UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/71 "2018-02-17T19:06:18Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![monsij](https://discuss.codechef.com/user_avatar/discuss.codechef.com/monsij/32/783_2.png) [@monsij](https://discuss.codechef.com/u/monsij)\
**Post date:** [February 17, 2018, 7:33pm UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/72 "2018-02-17T19:33:04Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![vijju123](https://discuss.codechef.com/user_avatar/discuss.codechef.com/vijju123/32/195207_2.png) [@vijju123](https://discuss.codechef.com/u/vijju123)\
**Post date:** [February 17, 2018, 7:55pm UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/73 "2018-02-17T19:55:17Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![arkhamknight1](https://discuss.codechef.com/user_avatar/discuss.codechef.com/arkhamknight1/32/292113_2.png) [@arkhamknight1](https://discuss.codechef.com/u/arkhamknight1)\
**Post date:** [August 3, 2020, 12:33pm UTC](https://discuss.codechef.com/t/poinpoly-editorial/17995/74 "2020-08-03T12:33:59Z")

</div>

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

[Previous page](https://discuss.codechef.com/t/poinpoly-editorial/17995.md?page=3)
