Splitting the Field

题目描述

约翰农夫的 $N$ 头奶牛（$3 \leq N \leq 50,000$）位于他二维牧场中互不相同的位置。FJ 想用一个边与 $x$、$y$ 轴平行的矩形围栏把所有奶牛围起来，并且希望这个围栏尽可能小，从而包含每一头奶牛（允许奶牛在边界上）。

不幸的是，由于上个季度牛奶产量低，FJ 预算紧张。因此他希望围住更小的总面积以降低维护成本，而他能想到的唯一方法是建造两个围栏而不是一个。请帮助他计算：使用两个围栏而不是一个围栏时，他总共可以少围住多少面积。

与原来的围栏类似，这两个围栏必须在一起覆盖所有奶牛（允许奶牛在边界上），并且边都必须与 $x$、$y$ 轴平行。这两个围栏不允许相互重叠——甚至边界也不能重合。注意，面积为零的围栏是合法的，例如围栏的宽度和/或高度为零时。

输入格式

第一行输入 $N$。接下来 $N$ 行每行包含两个整数，表示一头奶牛的位置。奶牛位置为正整数，范围在 $1 \ldots 1,000,000,000$。

输出格式

输出一个整数，表示使用两个围栏而不是一个围栏时，FJ 可以节省的总面积。

6
4 2
8 10
1 1
9 12
14 7
2 3

107

提示

Problem credits: Brian Dean

标签: USACO|2016|Gold

来源

USACO|2016|Gold