격자좌표평면에 $n$개의 점이 있다. 모든 점은 정수좌표를 가지고 각 점의 $x$ 좌표는 모두 다르다. 그리고 각 점의 $y$좌표도 모두 다르다. 원점$(0, 0)$로부터 출발하여 $n$개의 점을 모두 방문하고 다시 원점으로 돌아오는 tour을 하고자 한다. 이 tour의 과정을 모니터에 나타내려고 하는데 요즘 LCD, LED, OLED 등의 모니터는 디지털로 표현할 수 밖에 없기 때문에 직선을 정확히 표현할 수 없고 픽셀 단위로 계단식으로 표현할 수 밖에 없다. 예를 들어 원점인 $(0, 0)$에서 $(2, 5)$로 이동한다면 다음과 같이 6개의 픽셀을 이용하여 경로를 표시해야 한다.

만약 원점에서 $(3, 3)$으로 이동한다면 3개의 픽셀로 표현할 수 있다.

두 점을 연결할 때 경로를 표시하는데 사용되는 픽셀을 결정하는 알고리즘은 두 점을 연결하는 가상의 선을 긋고 이 선이 픽셀의 내부를 조금이라도 지나면 해당 픽셀은 경로를 표시하는데 활용된다. 이와 같이 경로를 표시하는데 활용되는 픽셀의 수가 많을 수록 전력 소비가 많아진다. 따라서 두 점을 연결하는 경로를 표현하는데 사용하는 픽셀의 수를 두 점의 "픽셀 거리"라 하자. tour 경로를 애니메이션으로 표시할 때 원점에서 첫 점으로 이동하는 과정을 경로상에 있는 픽셀의 색을 칠하는 것으로 표현한다. 첫 점에 도착했을 때, 이 경로의 색을 지우고 다시 두 번째 점으로 이동할 때 그 경로상의 픽셀에 색을 칠하는 순서로 도착점까지 애니메이션 처럼 표현한다. 경곽이는 원점에서 출발하여 $n$개의 점을 모두 돌아 오는 tour 애니메이션을 제작하는데 쓰는 전력량을 최소화하고자 한다. 즉, 각 점간의 이동경로 상에 사용되는 픽셀의 수를 최소화 하고자 한다. 쉽게 말하면 "픽셀 거리" 합을 최소화하고자 한다. 단, 애니메이션에 나타나는 경로를 아름답게 하기 위하여 방문한 순서대로 좌표를 나열할 때, $x$값의 변화는 한 번을 제외하고는 이전과 같아야 한다. 즉, $n$개의 점의 방문 순서를 $x$를 기준으로만 나열했을 때, [출발점] - [x값 증가] - [x값 증가] - ... - [x 값 증가] - [x 값 감소] - ... - [x값 감소] - [출발점] 빨간색으로 표시된 것 처럼 증가에서 감소로 바뀌는 점을 단 한 번만 허용하고자 한다. 위 조건을 만족하면서 최소 픽셀거리의 합을 구하는 프로그램을 작성하시오.

tourist 애니메이션

문제 설명

입력

출력

예제

코드 제출

로그인

LOGIN