USACO2014DEC 铜组第一题

题目描述

农夫约翰（Farmer John）对奶牛的健康状况不满，于是为它们报名了各种体能活动。他的获奖奶牛贝茜（Bessie）参加了跑步课，需要跑一场穿过城市街区的马拉松。

马拉松路线包含 ( N ) 个检查点（( 3 <= N <= 100,000 ) ），必须按顺序访问，检查点 1 是起点，检查点 ( N ) 是终点。贝茜本应逐个访问所有检查点，但为了偷懒，她决定最多跳过一个检查点（不能跳过检查点 1 或 ( N ) ，否则太明显 ），以缩短总路程。

请帮助贝茜计算，跳过最多一个检查点后，她需要跑的最小总距离。

距离计算：两个检查点 ((x1, y1)) 和 ((x2, y2)) 之间的距离是曼哈顿距离，公式为 ( |x1 - x2| + |y1 - y2| ) 。

输入格式

• 第 1 行：整数 ( N )（检查点数量 ）。
• 第 2 至 ( N+1 ) 行：每行两个整数 ( x ) 和 ( y )，表示第 ( i ) 个检查点的坐标（( -1000 <= x, y <= 1000 ) ）。

样例输入

4
0 0
8 3
11 -1
10 0

输入详情
4 个检查点，坐标依次为 ((0,0))、((8,3))、((11,-1))、((10,0)) 。

输出格式

输出跳过最多一个检查点后，贝茜需要跑的最小总距离。

样例输出

14

输出详情
跳过第二个检查点 ((8,3)) 后，总路程为：

• 从检查点 1 到 3：( |0-11| + |0 - (-1)| = 11 + 1 = 12 )
• 从检查点 3 到 4：( |11-10| + |-1 - 0| = 1 + 1 = 2 )
  总距离 ( 12 + 2 = 14 ) ，为最优解。