The problem
A field on a map is a simple polygon: its edges meet only at shared corners. You get its corners as (x, y) pairs of whole numbers, in order round the edge, clockwise or counterclockwise. Return how many points with whole-number coordinates lie strictly inside the field (not on an edge).
inside_points([(0, 0), (4, 0), (4, 4), (0, 4)]) # 9
inside_points([(0, 0), (5, 0), (0, 5)]) # 6
inside_points([(0, 0), (1, 0), (0, 1)]) # 0
A corner may lie on the straight line between its two neighbours. The polygon has at least three corners and some area.
Limits
- Up to 100,000 corners, with coordinates up to about 10¹⁰ in size. Trying every point of the map is far too slow.
- Keep to whole numbers: a float area loses digits here.
Builds on GEOM-1 Points, vectors and the cross product.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | A square | Not run | |
| 2 | Clockwise | Not run | |
| 3 | A triangle | Not run | |
| 4 | Slanted edges | Not run | |
| 5 | Too thin | Not run | |
| 6 | Negative coordinates | Not run | |
| 7 | A corner on a straight edge | Not run | |
| 8 | An L shape | Not run | |
| 9 | A huge triangle | Not run | |
| 10 | 100,000 corners | Not run |