P10763 [BalticOI 2024] Tiles

Translated from [BalticOI 2024 Day2 T2](https://boi2024.lmio.lt/tasks/d2-tiles-statement.pdf).

There is a cathedral with $N$ vertices, whose coordinates are $(x_i,y_i)$ in order. For each $1 \leq i < N$, there is an edge between $i$ and $i+1$. In addition, there is an edge between $N$ and $1$. Each edge of the cathedral is parallel to the $x$ axis or the $y$ axis. Also, the cathedral is a simple polygon, meaning that: - Each vertex is incident to exactly two edges. - Any pair of edges can intersect only at a vertex. You have infinitely many $2 \times 2$ tiles, and you want to use these tiles to cover most of the cathedral region. More precisely, you want to choose a vertical line and cover the part of the cathedral to the left of that line. For any integer $k$, let $L_k$ be the vertical line that contains the points with $x$ coordinate equal to $k$. Covering the part of the cathedral to the left of $L_k$ means placing some tiles on the plane such that: - Every point inside the polygon with $x$ coordinate less than $k$ is covered by some tile. - No point outside the polygon, or with $x$ coordinate greater than $k$, is covered by any tile. - The interiors of the tiles do not overlap. The minimum $x$ coordinate among all vertices of the cathedral is $0$. Let $M$ be the maximum $x$ coordinate among all vertices of the cathedral. Please find the maximum $k\ (0 \leq k \leq M)$ that satisfies the conditions. By definition, an answer of $0$ always exists.

The first line contains two integers $N,M$. The next $N$ lines each contain two integers $(x_i,y_i)$. The vertices are given in clockwise or counterclockwise order.

Output the answer $k$.

| Subtask ID | Special Property | Score | | :----------: | :----------: | :----------: | | $1$ | $N=4$ | $4$ | | $2$ | $N \leq 6$ | $9$ | | $3$ | $x_N=0,y_N=0$，for $1 \leq i \leq N-2$，$x_i \leq x_{i+1},y_i \geq y_{i+1}$ | $11$ | | $4$ | $M \leq 1000$ and $y_i \leq 1000$ | $19$ | | $5$ | All $y_i$ are even | $22$ | | $6$ | All $x_i$ are even | $25$ | | $7$ | No special property | $10$ | For all testdata, $4 \leq N \leq 2 \times 10^5$, $1 \leq M \leq 10^9$, $0 \leq y_i \leq 10^9$, $\min(\{x_i\}) = 0,\max(\{x_i\}) = M$. For Sample 1, below is the covering for $k=2$.  You can see that this is the largest possible case. For Sample 2, there is no positive $k$ such that the part of the cathedral to the left of $L_k$ can be covered with tiles. For Sample 3, the diagram is as follows.  Translated by ChatGPT 5