luogu#P10251. 农场

    ID: 14210 远端评测题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 2 上传者: 标签>洛谷原创O2优化洛谷月赛循环结构

农场

题目背景

加入 mc2b2t.com 谢谢喵。

upd:

题目描述

ZHY 想管理他的农场。

具体地,他有 nn 片农场,每一片农场都是一个矩形,其四条边都平行于坐标轴。这些农场可以有重叠的部分。

他现在想圈一块地来维护自己的农场。他希望这块地可以完全覆盖所有农场。为了方便,他还希望这块地也是一个四条边都平行于坐标轴的矩形。他想最小化矩形的面积。

由于他的农场实在是太多了,所以他向你寻求帮助。你需要输出这个矩形的面积。

输入格式

第一行一个正整数 nn

接下来 nn 行,输入四个整数 x1,y1,x2,y2x_{1},y_{1},x_{2},y_{2},表示存在一个以 (x1,y1)(x_{1},y_{1})(x2,y2)(x_{2},y_{2}) 为两个对角顶点的农场。

输出格式

输出一个整数表示圈地的最小面积。

2
1 0 2 3
-1 1 3 2
12

提示

样例解释:如下图所示,绿色为第一个农场,红色为第二个农场,不难发现最小的圈地面积为 3×4=123\times 4=12


对于 40%40\% 的数据,n,x,y200n,|x|,|y| \le 200

对于 100%100\% 的数据,1n2×1051 \le n \le 2 \times 10^{5}0x,y1090 \le |x|,|y| \le 10^{9}x1x2x_{1}\neq x_{2}y1y2y_{1}\neq y_{2}