题解

题目描述

小美在平面上画了 $n$ 个封闭图形，每个图形由若干点描述。激光打印机需要按顺序打印这些图形，打印每个图形时需移动激光发射器到该图形的一个点，并以特定速度绘制。所有图形打印完毕后需返回初始点。求完成所有打印的最短时间。

解题思路

1. 计算周长：每个图形的周长由输入点按顺序连接形成闭合路径的长度决定。
2. 枚举排列顺序：所有可能的图形打印顺序，共 $n!$ 种情况。

题目内容

小美在纸上面了 $n$ 个封闭图形，编号为 $1,2,...,n$，第 $i$ 个图形由 $m_i$ 个点描述，他正在捣鼓他的激光打印机打印出这些图形。

这个打印机可以在平面上连续的移动打印，依靠激光发射器实现，激光发射器初始可以位于平面上的任意一个点 $S_0$ ，随后，由你确定打印顺序，按以下步骤依次打印这 $n$ 个图形：

• 记当前打印的图形编号为 $i$

• 将激光发射器以 $x$ 个单位长度每秒的速度移动到 $m_i$ 点中的其中一个(任选)，作为起始端点 $S_i$ ；

• 将激光发射器以 $y_i$ 个单位长度每秒的速度任意的在纸上移动，直到经过全部 $m_i$ 个点后回到起始端点 $S_i$ ；

• 打印过程中不能暂停；若经过非当前图形的点，忽略不计；

特别的，如果全部图像打印完毕，则将激光发射器以 $x$ 个单位长度每秒的速度移动到起始选择的点$S_0$ ，完成打印。

直接输出整个打印过程需要的最少时间。特别的，如果图形存在重叠，你需要重复打印重叠的部分。

输入描述

第一行输入两个整数 $n,x(3≦n≤7;1≦x≦1000)$ 代表图形数量，不打印时激光发射器的移动速度。

第二行输入 $n$ 个整数$y_1,y_2,...,y_n(1≦y_i≦1000)$ 代表激光发射器打印第 $i$ 个图形的移动速度。

此后，对于第 $i$ 个封闭图形，描述如下：

第一行输入一个整数 $m_i(3≦m_i≦7)$ 代构成该图形的点的数量。

此后 $m_i$ 行，每行输入两个整数 $a,b(-1000≦a,b≦1000)$ 代表点 $(a,b)$ 。保证同一个图形中没有重复的点。

输出描述

输出一个整数，代表最少时间。由于实数的计算存在误差，当误差的量级不超过 $10^{-6}$ 时，您的答案都将被接受，具体来说，设您的答案为 $a$ ，标准答案为 $b$ ，当且仅当 $\frac {∣a-b∣} {max(1,∣b∣)}≤10^{-6}$ 时，您的答案都将被接受。

样例1

输入

3 1
1 2 1
3
-3 3
0 0
-3 -2
3
1 3
3 0
1 -3
4
-2 1
4 3
5 -2
-3 -5

输出

54.507981260725

说明

在这一样例中，以点 $C$ 作为起点 $S_0$ 。依次打印图形一、三、二，具体路径描述如下：

首先打印图形一 $(C→A→B→C)$ ，耗时 $\frac {3\sqrt{2}+5+\sqrt{13}} {1} ≈12.84819196$ 。

随后打印图形三 $(C→G→B→I→J→G)$，耗时 $\frac {\sqrt{40}+\sqrt{26}+\sqrt{73}+\sqrt{37}}{1}$$≈26.05034111$。

最后打印图形二 $(G→D→E→F→D→A)$，耗时 $\frac {6+\sqrt{13}+\sqrt{13}}{2}$$≈6.60555128$ 。

别忘了加上图形与图形间的移动时间，这一部分耗时 $\frac {\sqrt{5}+\sqrt{13}+\sqrt{10}}{1}$$≈9.00359691$ 。