Square Pasture

题目描述

农夫约翰决定更新他的农场以简化其几何结构。 之前，他的奶牛在两个矩形的围栏牧场中吃草。农夫约翰希望用一个面积最小的正方形围栏牧场替换它们，并且该正方形仍能覆盖原先两道围栏所围住的农场区域。 请帮助农夫约翰求出他的新正方形牧场所需的最小面积，使得只要将其放置在合适的位置，它就仍然能够覆盖原先两个矩形牧场覆盖的全部区域。该正方形牧场的边应与 x 轴和 y 轴平行。

输入格式

输入格式（文件 square.in）： 输入文件第一行给出其中一个原矩形牧场，包含四个用空格分隔的整数 $x_1$ $y_1$ $x_2$ $y_2$，每个都在 $0 \ldots 10$ 的范围内。牧场的左下角在点 $(x_1, y_1)$，右上角在点 $(x_2, y_2)$，其中 $x_2 > x_1$ 且 $y_2 > y_1$。 输入文件第二行与第一行格式相同，给出第二个原矩形牧场。该牧场不会与第一个牧场重叠或接触。

输出格式

输出格式（文件 square.out）： 输出应为一行，包含一个整数，表示能够覆盖两个原矩形牧场所围区域的正方形牧场所需的最小面积。

6 6 8 8
1 8 4 9

49

提示

在上面的例子中，第一个原矩形的角为 $(6,6)$ 和 $(8,8)$。第二个的角为 $(1,8)$ 和 $(4,9)$。画出一条边长为 7 的正方形围栏，其角为 $(1,6)$ 和 $(8,13)$，则原来的区域仍可被围住；而且这是最优的，因为不可能用边长仅为 6 的正方形围住原区域。注意，边长为 7 的正方形有多种不同的合法放置方式，因为它可以在竖直方向稍微平移一些。 题目鸣谢：Brian Dean

标签: USACO|2016|Bronze

来源

USACO|2016|Bronze