← 返回题目列表

Codeforces · 8/C

C. 寻找订单

中文机器翻译题面 查看原题

女孩莉娜喜欢一切都井然有序,处处寻找秩序。有一次,她为上大学做准备,发现房间里一片狼藉——她手提包里的所有物品都被扔在房间里。当然,她想把它们放回手提包里。问题是女孩不能一次携带两个以上的物体,也不能移动手提包。而且,如果他拿走了一个物体,她就不能把它放在手提包之外的任何地方——她固有的秩序感不允许她这样做。

您将获得手提包的坐标以及某些笛卡尔坐标系中物体的坐标。众所周知,女孩所用的时间等于物体点之间线段长度的平方,从而走过任意两个物体之间的距离。据了解,最初女孩和手提包的坐标是相同的。你被要求找到这样一个动作顺序,即女孩可以在最短的时间内将所有物品放回她的手提包中。

输入

输入文件的第一行包含手提包的坐标 xs、ys。第二行包含数字 n (1 ≤ n ≤ 24) — 女孩拥有的物体数量。接下来的 n 行包含对象的坐标。所有坐标的绝对值不超过100。所有给定的位置都不同。所有数字都是整数。

输出

在第一行中输出唯一的数字——女孩将物品放入手提包所需的最短时间。

在第二行中输出 Lena 可能的最佳方式。输入中的每个对象都由其索引号(从 1 到 n)描述,手提包的点由数字 0 描述。路径应以手提包的点开始和结束。如果有多个最佳路径,则打印其中任何一个。

示例

输入 #1

0 0
2
1 1
-1 1

输出 #1

8
0 1 2 0

输入 #2

1 1
3
4 3
3 4
0 0

输出 #2

32
0 1 2 0 3 0