CF594C Edo and Magnets

Edo 有 $n$ 个冰箱磁贴的收藏！ 他打算买一台冰箱，并把这些磁贴贴在冰箱门上。商店可以制作任意尺寸的冰箱门，只要满足以下限制：冰箱门必须是长方形，并且门的长和宽都必须为正整数。 Edo 已经想好了如何把磁贴贴在冰箱上。他在平面上引入了一个坐标系，每个磁贴用一个边平行于坐标轴的长方形表示。 现在他希望最多移除 $k$ 个磁贴（也可以全都保留），并将剩下的所有磁贴粘贴到冰箱门上，并且门的面积要尽可能小。只要一个磁贴的中心点在冰箱门上或在其边界上，就认为该磁贴被粘在了冰箱门上。所有剩下的磁贴在冰箱门上的相对位置，必须与方案中的保持一致。 下面解释一下最后两句话。假设我们要在冰箱上贴两个磁贴。如果方案中某个磁贴的左下角坐标为 $ (x_1, y_1) $，右上角为 $ (x_2, y_2) $，那么它的中心就在 $ \left(\frac{x_1+x_2}{2},\frac{y_1+y_2}{2}\right) $（可能不是整数）。所谓保持相对位置，就是说只能整体平移，也就是说任意两个磁贴在方案中的中心连线，与在冰箱上粘贴后的中心连线必须一致。 冰箱门的边也必须与坐标轴平行。

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 100000$，$0 \leq k \leq \min(10, n-1)$）——Edo 有的磁贴数量和最多允许移除的磁贴数。 接下来 $n$ 行描述磁贴的初始排布。每行四个整数 $x_1, y_1, x_2, y_2$（$1 \leq x_1 < x_2 \leq 10^9$，$1 \leq y_1 < y_2 \leq 10^9$），表示当前磁贴的左下角和右上角的坐标。磁贴之间可以部分重叠，甚至完全重合。

输出一个整数，表示可以贴至少 $n-k$ 个磁贴且保持相对位置时，最小的冰箱门面积。

在第一个测试样例中，最优解是移除第一个或第三个磁贴。如果我们移除第一个磁贴，剩下两个磁贴的中心分别在 $(2.5, 2.5)$ 和 $(3.5, 3.5)$。因此，一个宽度为 $1$，高度为 $1$ 的冰箱门就足够了，对应面积也为 $1$。 在第二个测试样例中，不论移除哪个磁贴，答案都不会改变，需要一个宽度和高度都为 $8$ 的冰箱门。 在第三个样例中，由于 $k=0$，不能移除任何磁贴。 由 ChatGPT 5 翻译