---

题解

问题理解

我们有一个边长为 $m$ 的正方形印章。
初始时印章左下角在 $(0,0)$（纸张左下角）。
但是第一次按下之前会先根据 $(x_1, y_1)$ 移动，所以第一次按下时左下角在 $(x_1, y_1)$。

第 $i$ 次按下时，左下角坐标为：

$\left( \sum_{k=1}^{i} x_k,\ \sum_{k=1}^{i} y_k \right)$

因为移动是累加的。

每次按下一个 $m \times m$ 的正方形，它的右上角相对于左下角偏移 $(m, m)$。

---

周长计算方法

题目保证最终所有正方形形成一个连通区域（由 $1 \le x_i, y_i \le m-1$ 保证）。

关键观察：
整个形状的周长 =
$ \text{所有正方形的总周长} - 2 \times (\text{相邻正方形之间的重叠边长之和}) $

但是这里有个更简单的方法：

考虑整个形状的“边界”：

• 最左边的边界由第一个正方形的左边界决定（因为所有正方形都向右或向上移动，不会向左/下）。
• 最下边的边界由第一个正方形的下边界决定。
• 最右边的边界由最后一个正方形的右边界决定。
• 最上边的边界由最后一个正方形的上边界决定。

实际上，因为所有正方形都是 $m \times m$，并且移动方向只能是右/上，所以形状是轴对齐的，并且是一个单调的连通块。

---

公式推导

设第 $i$ 个正方形的左下角为 $(X_i, Y_i)$，其中
$ X_i = \sum_{k=1}^{i} x_k,\quad Y_i = \sum_{k=1}^{i} y_k $

正方形 $i$ 覆盖范围：
$x \in [X_i, X_i + m],\quad y \in [Y_i, Y_i + m]$

---

整个形状的水平边界

• 最左边：$x = X_1$（第一个正方形的左边界）
• 最右边：$x = X_n + m$（最后一个正方形的右边界）

水平方向总长度 = $(X_n + m) - X_1$

---

整个形状的垂直边界

• 最下边：$y = Y_1$
• 最上边：$y = Y_n + m$

垂直方向总长度 = $(Y_n + m) - Y_1$

---

周长公式

矩形的周长公式：
[ P = 2 \times (\text{宽度} + \text{高度}) ]
这里“宽度”和“高度”是整个形状的外接矩形尺寸吗？

注意：形状不一定填满整个外接矩形，但因为移动是单调的，并且 $x_i, y_i \ge 1$，形状的“边界”其实就是这个外接矩形的边界，并且中间不会有空洞（由连通性和单调性保证）。

因此：
$ P = 2 \times \big[ (X_n + m - X_1) + (Y_n + m - Y_1) \big] $

但 $X_n = \sum_{i=1}^n x_i$，$Y_n = \sum_{i=1}^n y_i$。
所以：
$ P = 2 \times \left( \sum_{i=1}^n x_i + m - x_1 + \sum_{i=1}^n y_i + m - y_1 \right) $

注意 $X_1 = x_1$，$Y_1 = y_1$。

---

与标程对照

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> x(n), y(n);
    for(int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    int ans = 2 * (accumulate(x.begin(), x.end(), 0) + m - x[0] + accumulate(y.begin(), y.end(), 0) + m - y[0]);
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
    cin >> ttt;
    while(ttt--) {
        solve();
    }
}

标程计算的是：

int ans = 2 * (accumulate(x.begin(), x.end(), 0) + m - x[0] + accumulate(y.begin(), y.end(), 0) + m - y[0]);

其中：

• accumulate(x.begin(), x.end(), 0) = $\sum_{i=1}^n x_i$
• m - x[0] = $m - x_1$
• 对 $y$ 同理

正是我们的公式。

---

示例验证

例 1：
$n=4, m=3$
$x = [1,2,2,1],\ y = [1,2,1,2]$

$\sum x = 6,\ \sum y = 6$

$P = 2 \times [6 + 3 - 1 + 6 + 3 - 1] = 2 \times [5 + 5 + 6]?$ 等等，仔细算：

$6 + (3-1) = 8$ 对 $x$ 部分
$6 + (3-1) = 8$ 对 $y$ 部分

$P = 2 \times (8 + 8) = 32$ ✅

---

例 2：
$n=1, m=2$
$x=[1], y=[1]$

$\sum x = 1,\ \sum y = 1$

$P = 2 \times [1 + (2-1) + 1 + (2-1)] = 2 \times [1+1 + 1+1] = 2 \times 4 = 8$ ✅

---

例 3：
$n=6, m=7$
$x = [3,1,3,6,5,6],\ y = [6,1,1,6,4,1]$

$\sum x = 24,\ \sum y = 19$

$P = 2 \times [24 + (7-3) + 19 + (7-6)]$
$= 2 \times [24 + 4 + 19 + 1]$
$= 2 \times 48 = 96$ ✅

---

结论

周长公式很简单，因为形状正好是一个单调的轴对齐多边形，它的边界就是整个形状的外接矩形的边界，而外接矩形尺寸由第一个正方形的左下角和最后一个正方形的右上角决定。

最终公式：
$ \text{ans} = 2 \times \left( \sum_{i=1}^n x_i + \sum_{i=1}^n y_i + 2m - x_1 - y_1 \right) $

等价于标程的写法。