marathon

题目描述
地图上有N 个城市，一只奶牛要从1 号城市开始依次经过N 个城市，最终到达N 号城市。但是这只奶牛觉得这样太无聊了，所以它决定跳过其中的一个城市（但是不能跳过1 号和N 号城市），使得它从1 号城市开始，到达N 号城市所经过的总距离最小
每一个城市都有一个坐标，从城市(x1, y1) 到城市(x2, y2) 的距离为 |x1 - x2| + |y1 - y2|

输入

第一行一个数N，表示城市个数
接下一行N 行每行两个数x,y，表示每个城市的坐标

输出

一行一个数ans, 使得它从1 号城市开始，跳过某一个城市，到达N 号城市所经过的总距离最小

样例输入

4
0 0
8 3
11 -1
10 0

样例输出

14

Explanation
跳过2 号城市

数据范围限制

• 对于40% 的数据，N <= 1000。
• 对于100% 的数据，3 <= N <= 10^5，-10^3 <= x <= 10^3，-10^3 <= y <= 10^3。

TJ

直接暴力枚举。。。

BC

var
        x,y:array[0..100000]of longint;
        n,i,sum,ans:longint;
begin
        assign(input,'marathon.in');reset(input);
        assign(output,'marathon.out');rewrite(output);
        readln(n);
        ans:=maxlongint;
        for i:=1 to n do
        begin
                readln(x[i],y[i]);
                if i>1 then sum:=sum+abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
        end;
        for i:=2 to n-1 do
        if sum-abs(x[i]-x[i-1])-abs(y[i]-y[i-1])-abs(x[i]-x[i+1])-abs(y[i]-y[i+1])+abs(x[i-1]-x[i+1])+abs(y[i-1]-y[i+1])<ans then
        ans:=sum-abs(x[i]-x[i-1])-abs(y[i]-y[i-1])-abs(x[i]-x[i+1])-abs(y[i]-y[i+1])+abs(x[i-1]-x[i+1])+abs(y[i-1]-y[i+1]);
        writeln(ans);
        close(input);close(output);
end.