/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 433 点
問題文
高橋君は配送ドライバーとして働いています。今日の配送で関係する地点は全部で N 箇所あり、それぞれの地点には 1 から N までの番号が付けられています。地点 1 は配送センター（出発地点兼帰着地点）であり、地点 2 から地点 N までが荷物を届けるべき届け先です。
各地点 i は二次元平面上の座標 (X_i, Y_i) に位置しています。なお、異なる地点が同じ座標に位置することもあります。
高橋君は配送センター（地点 1）からスタートし、すべての届け先（地点 2 から地点 N）をちょうど 1 回ずつ訪問した後、配送センター（地点 1）に戻ってくる巡回ルートを計画しています。すなわち、(2, 3, \ldots, N) の順列 (p_1, p_2, \ldots, p_{N-1}) を 1 つ選び、
1 \to p_1 \to p_2 \to \cdots \to p_{N-1} \to 1
の順に移動します。
高橋君の配送トラックは、座標 (a, b) から座標 (c, d) へ直接移動するときの燃料コストが (a - c)^2 + (b - d)^2 で計算されます。
巡回ルート全体の燃料コストは、ルート上で連続する 2 地点間の移動コストの総和です。具体的には、上の巡回ルートにおける燃料コストは
\mathrm{dist}(1, p_1) + \sum_{k=1}^{N-2} \mathrm{dist}(p_k, p_{k+1}) + \mathrm{dist}(p_{N-1}, 1)
です。ここで \mathrm{dist}(i, j) = (X_i - X_j)^2 + (Y_i - Y_j)^2 は地点 i から地点 j への移動コストを表します。
高橋君は、届け先を訪問する順序を自由に決めることで、巡回ルート全体の燃料コストを最小にしたいと考えています。移動は巡回ルートに対して直接行います。別の地点や適当な座標を経由することはできません。
燃料コストの最小値を求めてください。
制約
- 2 \leq N \leq 16
- -1000 \leq X_i \leq 1000 \quad (1 \leq i \leq N)
- -1000 \leq Y_i \leq 1000 \quad (1 \leq i \leq N)
- 入力はすべて整数である
入力
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
- 1 行目には、地点の数を表す整数 N が与えられる。
- 2 行目から N + 1 行目では、各地点の座標が与えられる。
- 1 + i 行目では、地点 i の x 座標 X_i と y 座標 Y_i がスペース区切りで与えられる。
出力
巡回ルート全体の燃料コストの最小値を整数で 1 行に出力せよ。
入力例 1
2 0 0 1 1
出力例 1
4
入力例 2
4 0 0 1 0 1 1 0 1
出力例 2
4
入力例 3
5 0 0 3 0 3 4 -1 3 0 3
出力例 3
46
Score : 433 pts
Problem Statement
Takahashi works as a delivery driver. There are a total of N locations relevant to today's deliveries, each numbered from 1 to N. Location 1 is the distribution center (serving as both the starting point and the return point), and locations 2 through N are the destinations where packages must be delivered.
Each location i is positioned at coordinates (X_i, Y_i) on a two-dimensional plane. Note that different locations may share the same coordinates.
Takahashi plans a tour route starting from the distribution center (location 1), visiting all destinations (locations 2 through N) exactly once each, and then returning to the distribution center (location 1). Specifically, he chooses a permutation (p_1, p_2, \ldots, p_{N-1}) of (2, 3, \ldots, N) and travels in the order:
1 \to p_1 \to p_2 \to \cdots \to p_{N-1} \to 1
The fuel cost for Takahashi's delivery truck to travel directly from coordinates (a, b) to coordinates (c, d) is calculated as (a - c)^2 + (b - d)^2.
The total fuel cost of the tour route is the sum of the travel costs between each pair of consecutive locations along the route. Specifically, the fuel cost of the above tour route is:
\mathrm{dist}(1, p_1) + \sum_{k=1}^{N-2} \mathrm{dist}(p_k, p_{k+1}) + \mathrm{dist}(p_{N-1}, 1)
where \mathrm{dist}(i, j) = (X_i - X_j)^2 + (Y_i - Y_j)^2 represents the travel cost from location i to location j.
Takahashi wants to minimize the total fuel cost of the tour route by freely choosing the order in which he visits the destinations. Travel is done directly along the tour route; he cannot pass through other locations or arbitrary coordinates along the way.
Find the minimum fuel cost.
Constraints
- 2 \leq N \leq 16
- -1000 \leq X_i \leq 1000 \quad (1 \leq i \leq N)
- -1000 \leq Y_i \leq 1000 \quad (1 \leq i \leq N)
- All input values are integers
Input
N X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
- The first line contains an integer N representing the number of locations.
- Lines 2 through N + 1 give the coordinates of each location.
- Line 1 + i contains the x-coordinate X_i and the y-coordinate Y_i of location i, separated by a space.
Output
Output the minimum total fuel cost of the tour route as an integer on a single line.
Sample Input 1
2 0 0 1 1
Sample Output 1
4
Sample Input 2
4 0 0 1 0 1 1 0 1
Sample Output 2
4
Sample Input 3
5 0 0 3 0 3 4 -1 3 0 3
Sample Output 3
46