P16777 [GKS 2020 #H] Rugby

在某个遥远的星球上，橄榄球在二维笛卡尔坐标系中无限地进行。球员只能占据整数格点，并且可以沿四个基本方向移动到相邻的格点。具体来说，如果一名球员当前位于点 $(X, Y)$，那么他可以在一步内移动到 $(X+1, Y)$、$(X-1, Y)$、$(X, Y+1)$ 或 $(X, Y-1)$。 比赛结束后，$N$ 名球员分散在坐标系中，任意格点要么空着，要么被一个或多个球员占据。他们想聚在一起拍照，排成一条由 $N$ 个格点组成的水平直线，每个点恰好有一名球员，且所有被占用的点彼此相邻。形式化地说，球员们需要移动，使得对于某个坐标 $X$ 和 $Y$，他们占据格点 $(X, Y)$、$(X+1, Y)$、$(X+2, Y)$、……、$(X+N-1, Y)$。假设球员可以自由选择直线的位置，且球员的排列顺序不重要，求球员们形成一条完美直线所需的最少总步数。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行给出球员人数 $N$。随后 $N$ 行给出球员的初始坐标。其中第 $i$ 行包含两个整数 $X_i$ 和 $Y_i$，表示第 $i$ 名球员的初始位置（$1 \le i \le N$）。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是球员们形成一条完美水平直线所需的最少总步数。

在第一个测试用例中，一种最优解是让第 $2$ 名球员向左移动 $2$ 步，向下移动 $3$ 步到达点 $(2, 1)$。 在第二个测试用例中，如果第 $1$ 名球员移动到点 $(0, 2)$，第 $3$ 名球员移动到点 $(2, 2)$，则可以用总共 $4$ 步形成一条完美直线。 ### 限制条件 **测试集 1** $1 \le N \le 10$。 $-500 \le X_i \le 500$。 $-500 \le Y_i \le 500$。 **测试集 2** 最多 $10$ 个测试用例满足 $1 \le N \le 10^5$。 其余测试用例满足 $1 \le N \le 10^4$。 $-10^9 \le X_i \le 10^9$。 $-10^9 \le Y_i \le 10^9$。 翻译由 DeepSeek V4 Pro 完成