CF85E Guard Towers

在一个遥远的王国里，住着一位非常贪婪的国王。为了保卫国土，他建造了 $n$ 座哨塔。除了这些哨塔以外，王国还有两支军队，每支军队都由一个专横且自恋的将军指挥。这两位将军互相看不顺眼，尤其是，他们绝不允许两支军队的士兵驻扎在同一座哨塔中。 在防御部署中，为了管理一座哨塔，将军必须派出自己军队的部分士兵驻扎在该塔。每位将军都会要求国王为管理哨塔支付一定的费用。由于他们生活在极为遥远的王国里，每位将军的计费方式也极为特殊：他会找到自己军队驻扎的最遥远的两座哨塔，并要求的费用等于这两座哨塔之间的距离。每座哨塔用平面上的坐标 $(x, y)$ 表示，两点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的距离定义为 $|x_1-x_2|+|y_1-y_2|$。 贪婪的国王对将军的收费标准并不满意，因此他只同意为两位将军支付其中较大的费用。然而，国王依然十分吝啬，他希望在所有可行的分配方式中，找到所需支付费用最少的一种。并且，每座哨塔必须恰好被一位将军的士兵驻守。 他雇佣了你帮他完成这个任务。你需要找出最少需要支付的费用。同时，由于国王十分严谨，你还需要统计有多少种分配方式能够达到这个最低费用。由于分配方式的数量可能非常大，请将结果对 $10^9+7$ 取模。 如果第一位将军占领的哨塔集合不同，则两种分配方案视为不同。

第一行包含一个整数 $n$ ($2\leq n \leq 5000$)，表示哨塔的数量。接下来 $n$ 行，每行包含两个整数 $x,y$，代表第 $i$ 个哨塔的坐标 $(0 \leq x, y \leq 5000)$。不存在两座哨塔在相同的点上。 Pretest 6 是该题目的最大测试之一。

第一行输出能支付给两位将军的最少费用。 第二行输出达到这一最小费用的分配方式数。答案对 $1000000007$ ($10^9+7$) 取模。

在第一个样例中，只有两座哨塔，它们之间的距离为 2。如果把两座哨塔都分配给一位将军，那么需支付的费用为 2。如果每位将军各管一座，费用则为 0。这是最小的可能费用。很容易发现，一共有两种分配方式可以达到这一费用。 由 ChatGPT 5 翻译