2022-4-14马拉松

1.利用pair记录坐标

2.计算总和sum

3.找到少走的最大路长

#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;//创建容器
#define x first
#define y second
const int N = 100100;
PII res[N];            //容器数组
int n;
int dis(PII a,PII b)
{
    return abs(a.x-b.x)+abs(a.y-b.y);  //计算距离
}
int main()
{
    scanf("%d",&n);
    int sum = 0;
    for(int i=1;i<=n;i++) {
        cin>>res[i].x>>res[i].y;
        if(i>1) sum+=dis(res[i],res[i-1]);  //求总距离
    }
    int maxt = 0;
    for(int i=2;i<n;i++) {
        int s = dis(res[i],res[i-1])+dis(res[i],res[i+1])-dis(res[i-1],res[i+1]);
        maxt = max(maxt,s);    //找到最大·的能少走的路
    }
    cout<<sum-maxt;
    return 0;
}