#P16967. [SGU445] Dig or Climb

    ID: 16175 传统题 250ms 256MiB 尝试: 3 已通过: 1 难度: 6 上传者: 标签>CF2000动态规划计算几何图论搜索DFS算法基础构造

[SGU445] Dig or Climb

题目描述

国王 Benjamin Forest VIII 的朋友 Nod 住在远方的村庄里。Nod 病得很重,国王命令 Red 尽快把药送到村庄。

从地图的俯视方向看,Red 决定始终沿城堡到村庄的直线方向前进。把这条直线对应的地形剖面画出来后,可以得到一条由 nn 个点组成的折线:

Pi=(xi,yi)P_i=(x_i,y_i),且 x1<x2<⋯<xnx_1<x_2<\cdots<x_n。

城堡位于 P1P_1,村庄位于 PnP_n。

Red 有两种移动方式:

  • 沿地表折线行走,速度为 vwv_w;
  • 在山体内部开凿水平隧道,速度为 vcv_c。隧道除端点外必须严格位于山体内部。

Red 可以任意选择在哪里沿地表行走、在哪里进入或离开水平隧道。求从城堡到村庄的最短时间。

输入格式

第一行一个整数 nn。

第二行两个整数 vw,vcv_w,v_c。

接下来 nn 行,第 ii 行两个实数 xi,yix_i,y_i,表示第 ii 个折点。

保证:

  • 1≤n≤10001\le n\le1000;
  • 1≤vw,vc≤101\le v_w,v_c\le10;
  • −10000≤xi,yi≤10000-10000\le x_i,y_i\le10000;
  • 对任意 i<ji<j,有 xi<xjx_i<x_j。

输出格式

输出一个实数,表示最短时间。

答案允许任意位小数,只要绝对误差不超过 10−610^{-6}。

样例

3
2 1
0 0
50 50
100 0
70.710678
3
1 2
0 0
50 50
100 0
50.000000