← All solutions

Shortest judge solution: 3798 bytes. Shortest team solution (during contest): N/A.

This was probably the hardest problem in the set (at least it was the one I struggled the most with). The basic idea, which is completely standard, is to simply try “all” possible grid placements and see which one gives the best result.

Let us write m ≤ 10 for the maximum number of grid tiles in any row/column of the grid (well, in some cases 11 tiles might be needed but never mind).

To execute this idea, we first have to find a reasonably small set of candidate grid placements. Consider an optimal grid placement. By shifting it to the left as far as possible, we may assume that one of the following two cases occur.

• Case 1: a vertex of the polygon lies on a vertical line L of the grid. In this case, consider shifting the polygon upwards, keeping the vertex on the vertical line. By a similar argument, one of the following two happens:
  • Case 1a: a vertex of the polygon lies on a horizontal line of the grid. There are only n² grid placements of this type: specifying which vertex lies on a vertical line and which vertex lies on a horizontal line completely specifies the grid.
  • Case 1b: a vertex of the grid lies on an edge e of the polygon (and the edge is not vertical). Suppose this grid vertex is t steps horizontally away from L. Then the grid vertex can be found by moving L horizontally a distance of t · x_s and intersecting it with the polygon edge. Trying all possible values of the polygon vertex that lies on L (n choices), the polygon edge e (n choices), and the offset t (m choices), this gives a total of at most n² m candidate placements.
• Case 2: a vertex of the grid lies on an edge of the polygon. Consider shifting the grid along the edge of the polygon (so that the vertex of the grid remains on that edge) as far as possible. Again, there are two possible outcomes:
  • Case 2a: a vertex of the polygon lies on a horizontal or vertical line of the grid. This case is analogous to case 1b (but possibly with a horizontal instead of a vertical line).
  • Case 2b: another vertex of the grid lies on some edge of the polygon, and this second polygon edge is not parallel to the first one. This case is somewhat similar to cases 1b and 2a, but now we need to guess both a vertical and a horizontal offset and then do intersection of the two polygon edges. This gives a total of at most n² m² candidate placements. The three test cases illustrated on the last page of this document were designed to trigger as many candidates of this form as possible.

This gives a set of O(n² m² ) candidate grid placements. It turns out that many of these candidates are the same, and one should take care to remove duplicates. I don’t have a good estimate for how much this saves, but on the judge data it tends to be around a factor 3-5, which might be sorely needed depending on how one solves the second part of the problem, described next. In the worst cases we had found, there are always less than 50 000 candidate grid placements after removing duplicates.

Given a candidate grid placement, we then need to figure out how many grid tiles it uses. The simplest way to do it would be to simply check for each grid tile whether it intersects the polygon. This is however too slow (time Ω(m² n) with pretty lousy constants), so something faster is needed. I went for a pretty messy flood-fill variant. The basic idea is to first trace through the polygon and mark the tiles that it passes through (in time O(mn) with pretty reasonable constants) and then do flood-fill to discover the rest of the tiles. Unfortunately this simple idea needs a bit of refinement to work correctly since one has to deal with polygon edges that run along the grid lines. This can be dealt with by also including the grid lines and grid vertices in the graph of tiles that we are flood-filling and with some careful coding one gets a correct (well, at least it passes the judge data) but somewhat sluggish solution.

A different (and faster!) approach is to do something reminiscent of a point-in-polygon test. For each row of tiles, find all x-coordinates where the polygon enters/exits the top of the row and all x-coordinates where it enters/exits the bottom of the row. Those tiles where the polygon either goes into the interior of the tile or has entered/exit the top/bottom an odd number of times will be used.

The last three test cases for Map Tiles

x_s = 100, y_s = 50.

x_s = 97, y_s = 93.

x_s = 97, y_s = 93.