许多电脑策略游戏都需要建造城市、招募军队、征服部落、收集资源。有时它会导致有趣的问题。
假设您的任务是建造一座方形城市。世界地图使用笛卡尔坐标。城市的侧面应与坐标轴平行。该地图包含具有宝贵资源的矿井,位于某些具有整数坐标的点。地雷的尺寸相对较小,即可以将其视为点。城市的建设应使所有地雷都位于城市广场内部或边缘。
建造城市需要大量资金,具体取决于城市的大小,因此您必须以最小的面积建造城市。给定地雷的位置,找出城市的最小可能面积。
输入
输入的第一行包含数字 n — 地图上的地雷数量 (2 ≤ n ≤ 1000)。接下来的 n 行中的每一行都包含一对整数 xi 和 yi - 相应矿井的坐标 (- 109 ≤ xi, yi ≤ 109)。所有点都是成对不同的。
输出
打印能够覆盖所有具有宝贵资源的矿山的城市最小面积。
示例
输入 #1
2 0 0 2 2
输出 #1
4
输入 #2
2 0 0 0 3
输出 #2
9