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;
}