Cow Checklist

题目描述

每天，农夫 John 会穿过牧场，检查每一头奶牛的健康状况。他的农场里有两种品种的奶牛：荷斯坦牛（Holsteins）和更赛牛（Guernseys）。他的 $H$ 头荷斯坦牛方便地编号为 $1 \ldots H$，他的 $G$ 头更赛牛方便地编号为 $1 \ldots G$（$1 \leq H \leq 1000, 1 \leq G \leq 1000$）。每头奶牛位于二维平面上的一个点（不一定互不相同）。 农夫 John 的巡查从荷斯坦牛 1 开始，并以荷斯坦牛 $H$ 结束。他希望沿途访问每一头奶牛。为了方便维护已访问奶牛的清单，他希望按照编号顺序访问荷斯坦牛和更赛牛。在他访问的所有 $H+G$ 头奶牛的序列中，编号为 $1 \ldots H$ 的荷斯坦牛应当作为一个（不一定连续的）子序列出现，更赛牛同理。换句话说，访问的 $H+G$ 头奶牛的序列应由将荷斯坦牛列表 $1 \ldots H$ 与更赛牛列表 $1 \ldots G$ 交错合并得到。 当农夫 John 从一头奶牛移动到另一头奶牛、行进距离为 $D$ 时，他会消耗 $D^2$ 的能量。请帮助他确定：按照上述方式完成巡查、访问所有奶牛所需的最小能量。

输入格式

第一行输入包含 $H$ 和 $G$，用空格分隔。 接下来的 $H$ 行包含 $H$ 头荷斯坦牛的 $x$ 和 $y$ 坐标；随后再接下来的 $G$ 行包含更赛牛的坐标。每个坐标都是 $0 \ldots 1000$ 范围内的整数。

输出格式

输出一行，给出农夫 John 访问所有奶牛的巡查路线所需的最小能量。

3 2
0 0
1 0
2 0
0 3
1 3

20

提示

题目来源：Brian Dean

标签: USACO|2016|Gold

来源

USACO|2016|Gold