P13709 [NWERC 2023] Jogging Tour

你可能知道，17 世纪时，一群荷兰人在曼哈顿岛建立了一个名为 New Amsterdam 的定居点，后来这里发展成了纽约市。 鲜为人知的是，另一群荷兰人也移居到了美洲，并建立了一座名为 *New Delft* 的城市。 和它更大的“兄弟”一样，New Delft 也建在由两组平行街道组成的网格上，这两组街道彼此垂直。 在 New Delft，已经有一些 stroopwafel 糕点店建成，但街道尚未修建。 你的任务是规划这些街道的网格布局。 为此，你需要确定网格的朝向，使得两组街道分别沿着两个正交的方向。 一旦确定了朝向，你可以任意修建街道，只要每条街道都沿着这两个方向之一，如图 J.1 所示。 每条街道都可以双向通行。  :::align{center} 图 J.1：样例输入 2 的示意图，展示了一种可能的街道布局，使得以某种顺序访问所有糕点店的最短路径长度最小。 ::: 街道布局应当为一年一度的 *Stroopwafel Run* 活动进行最优设计。 在该活动中，一组跑步者以任意顺序访问所有糕点店，他们可以在城市的任意地点开始和结束。 你的任务是设计一种网格布局，使得访问所有糕点店的最短路径长度尽可能短。

输入包括： - 一行一个整数 $n$（$2 \le n \le 12$），表示 New Delft 中 stroopwafel 糕点店的数量。 - 接下来 $n$ 行，每行两个整数 $x$ 和 $y$（$0 \le x, y \le 10^6$），表示一家糕点店的坐标。 所有糕点店的坐标均不相同，即对于任意 $1 \le i, j \le n$ 且 $i \neq j$，都有 $(x_i, y_i) \neq (x_j, y_j)$。

输出在最优网格布局下，访问所有糕点店的最短路径长度。 你的答案的绝对误差或相对误差不超过 $10^{-6}$。

由 ChatGPT 4.1 翻译