Background

Translated from BalticOI 2024 Day2 T2.

Problem Description

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.

Input Format

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 Format

Output the answer $k$.

14 6
0 1
0 3
2 3
2 4
0 4
0 6
3 6
3 7
4 7
6 7
6 5
3 5
3 2
3 1

2

4 3
0 0
0 3
3 3
3 0

0

18 9
0 2
2 2
2 1
4 1
4 0
9 0
9 2
4 2
4 4
7 4
7 3
9 3
9 6
4 6
4 5
2 5
2 4
0 4

6

Hint

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