[백준] 10655번: 마라톤 1

 

 

import sys
from itertools import combinations
input = sys.stdin.readline

n = int(input())
checkpoints = []

for _ in range(n):
    x, y = map(int, input().split())
    checkpoints.append([x, y])

answer = int(1e9)
for comb in combinations(checkpoints[1:-1], n-3):
    temp = []
    temp.append(checkpoints[0])
    temp += list(comb)
    temp.append(checkpoints[-1])
    distance = 0
    for i in range(n-2):
        x1, y1 = temp[i]
        x2, y2 = temp[i+1]
        distance += abs(x1-x2) + abs(y1-y2)
    answer = min(answer, distance)
print(answer)