1240 - 方形牧场(USACO 2016)

通过次数

20

提交次数

40

时间限制 : 1 秒
内存限制 : 128 MB

农夫约翰决定翻修他的农场以简化其几何形状。
以前,他的牛在两个栅栏围起来的长方形牧场上吃草。
现在,约翰想要用栅栏修建一个新的正方形牧场。
正方形牧场需要覆盖之前两个长方形牧场所包围的全部区域。
请你确定,新修建的正方形牧场的面积最小是多少。
正方形牧场的边应与 x 轴和 y 轴平行。

输入

第一行包含四个整数 x_1,y_1,x_2,y_2,表示第一个长方形牧场的左下角坐标 (x_1,y_1) 和右上角坐标 (x_2,y_2)。
第二行同样包含四个整数 x_1,y_1,x_2,y_2,表示第二个长方形牧场的左下角坐标 (x_1,y_1) 和右上角坐标 (x_2,y_2)。
两个牧场之间不会发生重叠或接触。

输出

输出能够覆盖之前两个长方形牧场所包围的全部区域的正方形牧场的最小面积。

样例

输入

6 6 8 8
1 8 4 9

输出

49

输入

4 0 7 1
1 6 7 8

输出

64

提示

0≤x_1< x_2 ≤10
0≤y_1< y_2 ≤10