← 返回题目列表

Codeforces · 594/C

C. 江户和磁铁

中文机器翻译题面 查看原题

Edo 收集了 n 个冰箱贴!

他决定买一台冰箱并将磁铁挂在门上。商店可以制造任何尺寸的冰箱,但必须满足以下限制:冰箱门必须是矩形,并且门的长度和宽度都必须是正整数。

Edo 想出了如何将磁铁放在冰箱上。他引入了平面坐标系,其中每个磁体都表示为一个边长与坐标轴平行的矩形。

现在他想移除不超过k块磁铁(他可能选择保留全部)并将所有剩余的磁铁贴在冰箱门上,并且门的面积要尽可能小。如果磁铁的中心位于门或其边界上,则认为磁铁附着在冰箱门上。所有剩余磁铁的相对位置必须与平面图相对应。

让我们解释一下最后两句话。假设我们想在冰箱上挂两块磁铁。如果平面图中的磁铁的坐标为左下角 (x1, y1) 和右上角 (x2, y2),则其中心位于 ($$\frac{x_{1}+x_{2}}{2}$$, $$\frac{y_{1}+y_{2}}{2}$$)(可以不是整数)。通过说相对位置应该对应于平面,我们的意思是唯一可用的操作是平移,即在原始平面中连接两个磁铁的中心的矢量必须等于在冰箱上连接这两个磁铁的中心的矢量。

冰箱门的侧面也必须与坐标轴平行。

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ min(10, n - 1)) - Edo 拥有的磁铁数量以及 Edo 不得在冰箱上放置磁铁的最大数量。

接下来的 n 行描述了放置磁铁的初始计划。每行包含四个整数 x1, y1, x2, y2 (1 ≤ x1 < x2 ≤ 109, 1 ≤ y1 < y2 ≤ 109)——当前磁铁的左下角和右上角的坐标。磁体可以部分重叠或者甚至完全重合。

输出

打印一个整数——冰箱门的最小面积,可用于放置至少 n - k 个磁铁,并保留相对位置。

示例

输入 #1

3 1
1 1 2 2
2 2 3 3
3 3 4 4

输出 #1

1

输入 #2

4 1
1 1 2 2
1 9 2 10
9 9 10 10
9 1 10 2

输出 #2

64

输入 #3

3 0
1 1 2 2
1 1 1000000000 1000000000
1 3 8 12

输出 #3

249999999000000001

注意

在第一个测试样本中,最好移除第一或第三个磁铁。如果我们移除第一个磁铁,另外两个磁铁的中心将位于点 (2.5, 2.5) 和 (3.5, 3.5) 处。这样,买一台门宽1、门高1的冰箱就够了,相应地,门的面积也等于1。

在第二个测试样本中,无论移除哪个磁铁,答案都不会改变——我们需要一台门宽为 8、门高为 8 的冰箱。

在第三个示例中,您无法删除任何内容,因为 k = 0。