首先确定每个点最后走到的是哪一个点。
这部分可以枚举全排列。
假设左上角的点为 \((x_0, y_0)\)，右上角的点为 \((x_1, y_1)\)，左下角的点为 \((x_2, y_2)\)，右下角的点为 \((x_3, y_3)\)。
令最终的点为 \((x'_0, y'_0)\)，以此类推。
那么最终的答案就是 \(\sum\limits_{i = 0}^3 |x_i - x'_i| + |y_i - y'_i|\)。
令 \(x'_0 = x'_2 = a\)，那么如果当 \(\min(x_0, x_2)\le a\le \max(x_0, x_2)\) 时，\(|x_0 - x'_0| + |x_2 - x'_2| = |x_0 - x_2|\)，这是最优的。
否则说如果不在这个区间中，多走出去 \(1\)，答案就会多 \(2\)。
对于 \(x'_1 = x'_3\) 也是同理的。
那么对于 \(x\) 这一维，要让 \(x_0, x_1\) 这 \(2\) 部分都取到最优，就对正方形边长 \(d\) 有个限制，\(\min(x_1, x_3) - \max(x_0, x_2)\le d\le \max(x_1, x_3) - \min(x_0, x_2)\)，注意还有个 \(d\ge 0\) 的限制。
否则如果 \(d\) 不在这个区间里，就只能让一个边取到最优，另一边则要扩展出去。
相应的，\(y\) 这一维对 \(d\) 也有个限制区间。
如果 \(x, y\) 限制区间有交，那么 \(d\) 取在交的这个区间内就可以让两维都取到最小值。
否则可以考虑使一边最优，另一边调整到这一边的区间内，且越少越好，例如当 \(r_x < l_y\) 时，将 \(d\) 调整到 \(r_x\) 或 \(l_y\) 时是最优的。
时间复杂度 \(O(Tn!n)\)。
代码
#include<bits/stdc++.h>
using i64 = long long;
int dx[4], dy[4], px[4], py[4];
inline void Main() {
for (int i = 0; i < 4; i++) scanf("%d%d", &dx[i], &dy[i]);
int p[4] = {0, 1, 2, 3};
i64 ans = 1e10;
do {
for (int i = 0; i < 4; i++) px[i] = dx[p[i]], py[i] = dy[p[i]];
int lx = std::min(px[1], px[3]) - std::max(px[0], px[2]), rx = std::max(px[1], px[3]) - std::min(px[0], px[2]);
int ly = std::min(py[0], py[1]) - std::max(py[2], py[3]), ry = std::max(py[0], py[1]) - std::min(py[2], py[3]);
if (rx < 0 || ry < 0) continue;
i64 tot = 0ll + abs(px[0] - px[2]) + abs(px[1] - px[3]) + abs(py[0] - py[1]) + abs(py[2] - py[3]);
if (rx < ly) tot += 2ll * (ly - rx);
if (ry < lx) tot += 2ll * (lx - ry);
ans = std::min(ans, tot);
} while (std::next_permutation(p, p + 4));
printf("%lld\n", ans);
}
int main() {
int T; scanf("%d", &T);
while (T--) Main();
return 0;
}