某工厂有一台数控加工设备,需要在平面上加工 n 个闭合轮廓。每个轮廓由若干顶点描述,顶点按输入顺序依次连接并首尾相连形成闭合折线。工具头在非加工状态下以速度 x 直线移动,加工第 i 个轮廓时以速度 yi 沿轮廓移动。加工一个轮廓时,必须从该轮廓某个顶点出发,沿闭合折线完整走一圈并回到该顶点。加工完所有轮廓后需返回第一个被加工轮廓的起点。求完成全部轮廓并返回起点所需的最短时间。
某工厂有一台数控加工设备,需要在平面上加工 n 个闭合轮廓。设备工具头在非加工状态下可以以固定速度 x 沿直线移动;加工第 i 个轮廓时,工具头沿轮廓移动的速度为 yi。
每个轮廓由若干个顶点描述。顶点按输入顺序依次连接,最后一个顶点再连回第一个顶点,形成一条闭合折线。第 i 个轮廓的加工时间等于该闭合折线的长度除以 yi。
加工一个轮廓时,必须选择该轮廓上的某个顶点作为起点,沿这条闭合折线完整走完一圈并回到该起点,加工过程不能停顿。两点之间的直线移动时间等于欧氏距离除以 x。
你需要决定轮廓的加工顺序以及每个轮廓的起点。加工从第一个被加工轮廓的起点开始,依次移动到各个轮廓的起点并完成加工;加工完最后一个轮廓后,还需要从最后轮廓的起点返回第一个被加工轮廓的起点。
请计算完成全部轮廓并返回起点所需的最少时间。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.