P5244 [USACO19FEB] Mowing Mischief P

Bessie’s cousins, Ella and Bella, are visiting the farm. Unfortunately, ever since they arrived, they have been causing trouble. In their latest scheme, they decide to mow as much grass as possible. The farm’s grassland is a $T \times T$ square. The lower-left corner is $(0,0)$, and the upper-right corner is $(T,T)$. Therefore, the square contains $(T+1)^2$ lattice points (points with integer coordinates). Ella and Bella plan to start from $(0,0)$ and run to $(T,T)$ at a speed of one unit length per second. At the same time, each cow holds one end of a very sharp and very elastic wire. Any area swept by this wire will have its grass cut. Ella and Bella may take different paths, but they will only move up or right, traveling from one lattice point to another. Bessie is very worried that too much grass will be cut, so she comes up with a clever plan to restrict Ella and Bella’s paths. There are $N$ flowers scattered across the grassland ($1 \leq N \leq 2 \times 10^5$), and each flower is located at a specific lattice point. Bessie will choose a subset $S$ of these flowers. Both Ella and Bella must pass through all flowers in $S$ (that is, both of their paths must go through every flower in $S$). Ella and Bella will cut an area of grass as large as possible. Please help Bessie determine the set $S$ so that, while $S$ is as large as possible, the **area** of grass that gets cut is minimized.

The first line contains two integers $N, T$ ($1 \leq T \leq 10^6$). The next $N$ lines each contain two integers $x_i, y_i$, representing the position of a flower. It is guaranteed that $1 \leq x_i, y_i \leq T-1$, and no two flowers lie on the same horizontal or vertical line.

Output one integer: the minimum possible **area** of grass that gets cut.

Choosing the flowers at positions $(10,3)$ and $(13,11)$ can minimize the area of grass that gets cut. Subtasks: For $20\%$ of the testdata, $N \leq 3200$. Translated by ChatGPT 5