Unhappy with the poor health of his cows, Farmer John enrolls them in an assortment of different physical fitness activities. His prize cow Bessie is enrolled in a running class, where she is eventually expected to run a marathon!

The marathon course consists of N checkpoints (3 <= N <= 100,000) to be visited in sequence, where checkpoint 1 is the starting location and checkpoint N is the finish. Bessie is supposed to visit all of these checkpoints one by one, but being the lazy cow she is, she decides that she will skip up to one checkpoint in order to shorten her total journey. She cannot skip checkpoints 1 or N.

Please help Bessie find the minimum distance that she has to run if she can skip up to one checkpoint.

Since the course is set in a downtown area with a grid of streets, the distance between two checkpoints at locations (x1, y1) and (x2, y2) is given by |x1-x2| + |y1-y2| ("Manhattan" distance).

Line 1: The value of N.

Lines 2..1+N: Each line contains two space-separated integers, x and y, representing a checkpoint (-1000 <= x,y <= 1000). The checkpoints are given in the order they must be visited. Several checkpoints may share the same physical location; skipping such a checkpoint skips only one instance.

The minimum distance that Bessie can run by skipping up to one checkpoint.

riseoj 작성

출처 올림피아드 > USACO > 2014-2015 > December > Bronze