배달 경로

몇 년간의 기록적인 우유 생산 끝에, 농부 존(Farmer John)은 이제 N개 (1 <= N <= 100)의 농장으로 이루어진 네트워크 전체를 운영하고 있다. 농장 i는 2차원 평면의 위치 (x_i, y_i)에 있으며, 다른 모든 농장과 위치가 다르고 x_i와 y_i는 모두 정수이다.

FJ는 N개의 농장에 물자를 배달하는 일일 배달 경로를 계획하는 데 당신의 도움이 필요하다. 농장 1에서 출발하여 농장들을 순서대로(농장 1, 그 다음 농장 2, 그 다음 농장 3, ...) 방문하고, 농장 N을 방문한 후 마지막으로 농장 1로 돌아올 계획이다. FJ가 북, 남, 동, 서 중 한 방향으로 한 걸음 이동하는 데는 1분이 걸린다. 또한 FJ는 전체 여정 동안 각 농장을 정확히 한 번씩만 방문하고 싶어 한다 (물론 두 번 방문하는 농장 1은 예외).

FJ가 전체 배달 경로를 완주하는 데 걸리는 최소 시간을 구하는 것을 도와주자.

첫째 줄: 농장의 수 N.

둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 공백으로 구분된 두 정수 x_i와 y_i (1 <= x_i, y_i <= 1,000,000)가 주어진다.

FJ가 배달 경로를 완주하는 데 필요한 최소 시간(분), 또는 (농장 1을 제외하고) 모든 농장을 정확히 한 번씩 방문하는 실현 가능한 배달 경로가 없으면 -1.

riseoj 작성

출처 올림피아드 > USACO > 2011-2012 > January > Silver