Blocked Billboard II

题目描述

奶牛 Bessie 曾经从她的牛棚里拥有很好的视野，望向路对面一组两块广告牌，上面宣传着看起来很美味的牛饲料。 不幸的是，其中一块广告牌最近更新了内容，现在改为宣传“Farmer Larry 的割草机”。Bessie 不喜欢割草机，因为据她所知，割草机存在的唯一目的就是修剪她田里那些她觉得很美味的草（如果你还没注意到，Bessie 的很多思考过程都围绕着食物）。 幸运的是，剩下那块牛饲料广告牌位于割草机广告牌的前方，可能会遮挡它。 Bessie 决心把这块令人反感的割草机广告牌从视野中完全移除，于是想出了一个冒险计划。她打算从牛棚里偷一块大的矩形篷布，深夜悄悄出去，把割草机广告牌仍然露出的部分盖住，使得她再也看不到它的任何部分。 给定两块广告牌的位置，请你帮助 Bessie 计算她所需篷布的最小面积。由于牛棚里可用的篷布只有矩形大小，Bessie 观察到她可能需要一块面积略大于割草机广告牌露出部分的篷布，如下方示例所示。篷布只能以其边与其他广告牌边平行的方式放置（即不能“倾斜”）。

输入格式

第一行输入包含四个用空格分隔的整数：$x_1$ $y_1$ $x_2$ $y_2$，其中 $(x_1, y_1)$ 和 $(x_2, y_2)$ 分别是割草机广告牌在 Bessie 的二维视野中左下角与右上角的坐标。 下一行包含另外四个整数，以同样方式给出牛饲料广告牌的左下角与右上角坐标。牛饲料广告牌可能遮挡割草机广告牌的全部、部分或完全不遮挡。所有坐标范围为 -1000 到 +1000。

输出格式

请输出 Bessie 需要使用的篷布的最小面积，使其覆盖割草机广告牌的部分区域，从而让该广告牌被完全遮挡。

2 1 7 4
5 -1 10 3

15

提示

这里，牛饲料广告牌遮挡了割草机广告牌的右下角，但这并没有真正帮上忙，因为 Bessie 仍然需要使用一块大小与整个割草机广告牌一样大的篷布。 题目致谢：Brian Dean

标签: USACO|2018|Bronze

来源

USACO|2018|Bronze