← 返回题目列表

Codeforces · 85/E

E. 守卫塔

中文机器翻译题面 查看原题

在一个遥远的王国里住着一位非常贪婪的国王。为了保卫他的土地,他建造了n座守卫塔。除了塔楼之外,王国还有两支军队,每支军队都由一位残暴且自恋的将军领导。将领们互相看不惯,具体来说,就是绝对不会让两军士兵同处一塔。

在管理守卫塔的防御行动中,将军必须派遣部分军队到该塔。每位将军都会向国王索要一些管理塔楼的费用。由于他们生活在一个非常遥远的王国,每个将军都以以下奇怪的方式评估他的费用:他找到两座最偏远(最远)的塔楼,那里是他军队的士兵所在的位置,并要求与距离相等的费用。每个塔都由平面上坐标为 (x, y) 的点表示,坐标为 (x1, y1) 和 (x2, y2) 的两点之间的距离在该王国中确定为 |x1 - x2| + |y1 - y2|。

贪婪的国王对将军们的这样的要求并不满意,所以他只同意为两名将军支付一笔费用,相当于最多两次要求的费用。然而,国王仍然贪得无厌,在军队之间布置塔楼的所有方法中,他想找到最便宜的一种。每个塔只能由一支军队的士兵占领。

他为此雇用了你。您应该找到足以支付费用的最低金额。而且国王也很谨慎,你也应该数一下需要花同样钱的安排有多少。由于它们的数量可能相当大,国王只要知道除以 109 + 7 的余数就足够了。

如果第一位将军的士兵占据的塔组不同,则两种排列是不同的。

输入

第一行包含一个整数n(2≤n≤5000),n是警卫塔的数量。接下来是 n 行,每行包含两个整数 x、y——第 i 个塔的坐标 (0 ≤ x, y ≤ 5000)。同一地点不存在两座塔。

预测试 6 是此问题的最大测试之一。

输出

在第一行打印足以向将军支付费用的尽可能少的金额。

在第二行写出可以使用尽可能少的费用进行的安排数量。该数字应以 1000000007 (109 + 7) 为模进行计算。

示例

输入 #1

2
0 0
1 1

输出 #1

0
2

输入 #2

4
0 0
0 1
1 0
1 1

输出 #2

1
4

输入 #3

3
0 0
1000 1000
5000 5000

输出 #3

2000
2

注意

在第一个例子中,只有两座塔,它们之间的距离等于 2。如果我们将两座塔都给一个将军,那么我们就必须支付 2 个单位的钱。如果每个将军都接收一座塔来管理,则费用将等于0。这是可能的最小费用。正如您所看到的,我们可以通过两种方式获取它。