Mowing Mischief

题目描述

贝茜的表妹 Ella 和 Bella 来农场做客。不幸的是，她们自从来了之后就一直在捣乱。 在她们最新的计划中，她们决定尽可能多地割草。农场最好的草地是一块边长为 $T \times T$ 的正方形。左下角为 $(0,0)$，右上角为 $(T,T)$。因此，这个正方形包含 $(T+1)^2$ 个格点（坐标为整数的点）。 Ella 和 Bella 计划都从 $(0,0)$ 出发，以单位速度跑到 $(T,T)$，同时各自握住一根非常锋利且非常有弹性的细线的一端。细线扫过的任意区域内的草都会被割掉。Ella 和 Bella 可以走不同的路径，但每条路径只能由向上和向右的步子组成，从一个格点移动到另一个格点。 贝茜担心会割掉太多草，于是想出了一个巧妙的办法来约束 Ella 和 Bella 的路径。草地上散布着 $N$ 朵美味的花（$1 \leq N \leq 2 \cdot 10^5$），每朵花都位于不同的格点上。贝茜会挑选一个花的集合 $S$，要求 Ella 和 Bella 都必须经过这些花（也就是说，Ella 的路径必须经过 $S$ 中所有的花，Bella 的路径也必须经过 $S$ 中所有的花）。为了在这些路径中加入尽可能多的“路标”，贝茜会在所有满足“能被一头从 $(0,0)$ 仅向上和向右移动到 $(T,T)$ 的牛访问”的花的子集中，选择大小尽可能大的集合 $S$。 在必须访问 $S$ 中花朵的限制下，Ella 和 Bella 会尽量最大化她们割到的草量。请帮助贝茜选择 $S$，使得被割掉的草量尽可能小。

输入格式

第一行包含 $N$ 和 $T$（$1 \leq T \leq 10^6$）。接下来的 $N$ 行每行包含一朵花的整数坐标 $(x_i, y_i)$。保证对所有 $i$，都有 $1 \leq x_i, y_i \leq T-1$，并且任意两朵花不在同一条水平线或同一条竖直线上。 在至少 20% 的测试用例中，额外保证 $N \leq 3200$。

输出格式

输出一个整数，表示可能的最小被割草面积。

5 20
19 1
2 6
9 15
10 3
13 11

117

提示

在上面的例子中，贝茜选择位于 $(10,3)$ 和 $(13,11)$ 的花是最优的。这样在最坏情况下，Ella 和 Bella 将会割到三块矩形草地，总面积为 $117$。 题目致谢：Dhruv Rohatgi

标签: USACO|2019|Platinum

来源

USACO|2019|Platinum