5716 - 城市路径
时间限制 : 1 秒
内存限制 : 256 MB
地图上有n个城市，一只奶牛要从1号城市开始依次经过这些城市，最终到达n号城市。但是这只奶牛觉得这样太无聊了，所以它决定跳过其中的一个城市（但是不能跳过1号和n号城市），使得它从1号城市开始，到达n号城市所经过的总距离最小。假设每一个城市i都有一个坐标（xi，yi），从（x1，y1）的城市到（x2，y2）的城市之间的距离为|x1x2-|+|y1-y2|。
输入
第1行1个正整数n，表示城市个数。
接下来的n行，每行2个数xi和yi，表示城市i的坐标。
输出
一行一个数，使得它从1号城市开始，跳过某一个城市，到达n号城市所经过的最小总距离。
样例
输入
4 0 0 8 3 11 -1 10 0
输出
14
提示
【样例说明】
跳过2号城市。
【数据规模】
对于40%的数据满足：n≤1000。
对于100%的数据满足：3≤n≤100000，-1000≤xi，yi≤1000。
来源
课课通