[Usaco2007 Feb]Building A New Barn新牛舍

经过多年的积蓄，农夫 John 决定建造一座新牛舍。他知道所有 $N$ 头牛的吃草位置，希望将牛舍建在最方便的地方。

第 $i$ 头牛位于整数点 $(X_i,Y_i)$。任意两头牛的位置互不相同，且不存在两头牛位于上下左右相邻的格点，即对于任意 $i\ne j$，均有：

$$|X_i-X_j|+|Y_i-Y_j|\ne 1。$$

John 必须将牛舍建在一个没有牛吃草的整数点 $(X,Y)$。第 $i$ 头牛到牛舍的距离定义为曼哈顿距离：

$$|X-X_i|+|Y-Y_i|。$$

请确定牛舍的位置，使所有牛到牛舍的距离之和最小，并求出能够达到这一最小距离和的牛舍位置数量。

输入格式

第一行包含一个整数 $N$，表示牛的数量。

接下来 $N$ 行，第 $i$ 行包含两个整数 $X_i,Y_i$，表示第 $i$ 头牛的吃草位置。

输出格式

输出一行两个整数，分别表示所有牛到牛舍的最小距离和，以及能够达到这一最小距离和的牛舍位置数量。

样例输入

4
1 -3
0 1
-2 1
1 -1

样例输出

10 4

数据范围

• $2\le N\le 10^4$；
• $-10^4\le X_i,Y_i\le 10^4$；
• 任意两头牛的位置互不相同；
• 对于任意 $i\ne j$，均有 $|X_i-X_j|+|Y_i-Y_j|\ne 1$。

来源与许可

本题为 USACO 2007 February 试题「新牛舍」，题面与测试数据整理自 BZOJ。

样例 1

输入

4
1 -3
0 1
-2 1
1 -1

输出

10 4