마라톤 (브론즈)

소들의 건강 상태가 좋지 않아 걱정인 농부 존은 소들을 다양한 체력 단련 활동에 등록시킨다. 그의 자랑스러운 소 베시는 달리기 수업에 등록되었고, 언젠가는 마라톤을 완주해야 한다!

마라톤 코스는 순서대로 방문해야 하는 N개의 체크포인트(3 <= N <= 100,000)로 이루어져 있으며, 체크포인트 1이 출발지이고 체크포인트 N이 결승점이다. 베시는 이 체크포인트들을 하나씩 모두 방문해야 하지만, 워낙 게으른 소라서 총 이동 거리를 줄이기 위해 체크포인트를 최대 하나까지 건너뛰기로 한다. 체크포인트 1과 N은 건너뛸 수 없다.

체크포인트를 최대 하나까지 건너뛸 수 있을 때, 베시가 달려야 하는 최소 거리를 구하는 것을 도와라.

코스는 격자형 도로가 있는 도심에 설정되어 있으므로, 위치 (x1, y1)과 (x2, y2)에 있는 두 체크포인트 사이의 거리는 |x1-x2| + |y1-y2|("맨해튼" 거리)로 주어진다.

첫째 줄: N의 값이 주어진다.

둘째 줄부터 1+N째 줄까지: 각 줄에 체크포인트를 나타내는 공백으로 구분된 두 정수 x와 y가 주어진다(-1000 <= x,y <= 1000). 체크포인트는 방문해야 하는 순서대로 주어진다. 여러 체크포인트가 물리적으로 같은 위치에 있을 수 있으며, 그런 체크포인트를 건너뛰는 것은 하나의 인스턴스만 건너뛰는 것이다.

체크포인트를 최대 하나까지 건너뛸 때 베시가 달릴 수 있는 최소 거리를 출력한다.

riseoj 작성

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