马拉松 - 题目详情

题目描述

农夫约翰对他的奶牛们的健康状况并不满意，于是给他的奶牛们报名了各种健身活动。

他最喜欢的奶牛贝茜被报名参加了一个跑步班。

在那里，她有希望在一场马拉松比赛中穿越约翰农场所在的城市的市中心。

马拉松线路由 $N$ 个检查点（编号 $1\sim N$ ）指定。

检查点 $1$ 是起点，检查点 $N$ 是终点，贝茜要按顺序经过每个检查点。

但是贝茜十分懒惰，所以她决定跳过其中一个检查点，以缩短她的整个行程。

但是，她不能跳过检查点 $1$ 和检查点 $N$ ，因为这太容易被人发现了。

在她可以跳过一个检查点的情况下，请确定她需要行进的最短距离。

由于该路线设置在市中心，街道呈网格状交错，因此两个检查站点 $(x_1,y_1)$ 与 $(x_2,y_2)$ 之间的距离应该为 $|x_1-x_2|+|y_1-y_2|$ 。

第一行包含整数 $N$ 。接下来 $N$ 行，每行包含两个整数 $x,y$ ，表示一个检查点的横纵坐标。检查点按 $1\sim N$ 的顺序给出。请注意，比赛线路可能存在交叉，在同一物理位置出现多个检查点。当贝茜跳过这样一个检查点时，她只跳过其中一个检查点，而不是跳过这个位置上的所有检查点。

输出贝茜可以跳过一个检查点的情况下，需要行进的最短距离。