CF1713A Traveling Salesman Problem 题解

题目链接：CF1713 Traveling Salesman Problem

题意：\(t\) 组数据，每组数据给定 \(n\) 个在坐标轴上的点 \((x_i,y_i)\) ，求最小的路径满足

• 起点和终点均为 \((0,0)\)
• 每一步只能走到 \((x+1,y),~(x-1,y),~(x,y+1),~(x,y-1)\)四者中的一个

例如下图

\(1 \le t \le 100,~1\le n \le 100,~-100 \le x_i,y_i \le 100\)

考虑四个方向上距离 \((0,0)\) 最远的所构成的合法矩形（满足走法的矩形）

对矩形进行一定的伸缩，一定能走完所有的点，并且一定是最优的，

例如题目里给出的这个图，如果 \((0,1)\) 有个点，也是可以走到的

显然， \((0,0)\) 也可以走到，然后就没了

时间复杂度 \(O(tn)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()
int n;
void solve()
{
    cin >> n;
    int minx=0,miny=0,maxx=0,maxy=0;
    for(int i=1,x,y; i<=n; i++)
    {
        cin >> x >> y;
        minx=min(x,minx);
        maxx=max(x,maxx);
        miny=min(y,miny);
        maxy=max(y,maxy);
    }
    cout << 2*(maxx+maxy-minx-miny) << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q;
    while(Q--) solve();
    return 0;
}