Informatica Online Judge

  마라톤 [1219 / 04C3]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 47   Total Tried : 409


The Champion of this Problem (C++) : gs17003 - 0ms / 571byte
My Best Submission (C++) : N/A

[]

Background

농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.

마라톤 코스는 N 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다.

게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한개를 몰래 건너뛰려 한다.

단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.

젖소 박승원이 체크포인트 한개를 건너뛰면서 달릴 수 있다면, 과연 승원이가 달려야 하는 최소 거리는 얼마일까?

참고로, 젖소 마라톤 대회는 도시 한복판에서 진행될 예정이기 때문에 거리는 택시 거리(Manhattan Distance)로 계산하려고 한다.

즉, (x1,y1)과 (x2,y2) 점 간의 거리는 |x1-x2| + |y1-y2| 로 표시할 수 있다. (|x|는 절댓값 기호다.)

Hints : 수행하는 연산이나 컴퓨터 등에 따라서 상황이 다르지만, 일반적으로 문제 풀이 시 컴퓨터는 1초에 대략 1억번의 연산을 한다고 가정을 하고 문제를 풉니다. 이 문제를 N^2에 비례하는 시간, 즉 100억 번의 연산을 통해서 해결하고자 한다면, 일반적으로 수행 시간이 100초 가량이 될 것이기 때문에 제한 시간 내에 문제를 못 풀수도 있습니다 - 정보과학 문제 해결 시에는 이러한 제한을 잘 분석하고 효율적인 프로그램을 만드는 것이 중요합니다.

Input

첫번째 줄에 체크포인트의 수 N이 주어진다.

이후 N개의 줄에 정수가 두개씩 주어진다. i번째 줄의 첫번째 정수는 체크포인트 i의 x 좌표, 두번째 정수는 y 좌표이다.

체크 포인트의 좌표는 겹칠 수도 있다 - 젖소 박승원은 체크포인트를 건너뛸 때 그 번호의 체크포인트만 건너뛰며, 그 점에 있는 모든 체크포인트를 건너뛰지 않는다.

[입력값의 정의역]
3 <= N <= 100,000
-1,000 <= x,y <= 1,000

[Sub-Task Info]
#1: N <= 1000 (40%)
#2: 추가 제한 조건은 없다. (60%)

Output

젖소 박승원이 체크포인트 1개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.

IO Example

입력
4
0 0
8 3
11 -1
10 0

출력
14

설명
젖소 박승원은 2번째 혹은 3번째 체크포인트를 건너뛸 수 있는데, 여기서 두번째 체크포인트를 건너뛸 경우 경로는 (0,0) -> (11,-1) -> (10,0) 이 되며 거리는 14이다. 박승원은 이것보다 더 짧게 달릴 수 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]