竹子战争

2013年11月6日1,8860

来源:http://218.5.5.242:9018/JudgeOnline/problem.php?id=1301

题目描述

      话说茅山道士散功重修已足足九九八十一天,这天子时,月上中天,道观前清辉点点。只听得訇然一声,闭关之处整个炸裂开来,烟雾散尽后,只见茅山道士纤尘不染地立于瓦砾之中,抬头望月,面上一片悲悯之色,喃喃道:“孽缘啊……”
果不其然,一名黑衣剑客从旁窜出,剑尖遥遥指向茅山道士,大喝道:“茅山妖道,我已在此等你多时,多年来的恩恩怨怨,就此了断吧!”言不及毕,左手捏了一个剑诀,便欺身上前,直攻茅山下盘。茅山道士看着黑衣剑客有些稚嫩的剑法,眼中掠过复杂的神色:“不如我们换个地方吧,你若能追得上我,我再和你大战一场!”说完向后纵身一跃,就此隐入竹林之中不知所踪。
      黑衣剑客知道茅山是个念旧的人,这次必然是要到竹林中的一处隐秘所在。但黑衣剑客的轻功并不高明,每次只能从一棵竹子顶端跳到水平距离不超过R,高度差不超过D的另一棵竹子顶端,所花的时间为两个顶点间的直线距离除以V。你能帮助黑衣剑客以最快的速度追上茅山道士么?
对于40%的数据 0<N<=20,0<=X,Y<=20
对于100%的数据 0<N<=1000,0<=X,Y<=1000,V>0

输入

第一行是四个整数N、R、D、V,表示竹子的数目、最大水平跳跃距离、最大竖直跳跃距离以及黑衣剑客飞行的速度。
接下来N行每行三个整数X、Y、H,表示每棵竹子的坐标及高度,高度大于0。
你可以假定起点在1,终点在N。
同一坐标可能有不同竹子。

输出

输出文件只有一行,为从1到N的最短时间。保留小数点后三位输出。
如果无法到达终点则输出”No Solution”。

样例输入

3 3 4 4 0 0 1 0 3 5 3 3 1

样例输出

2.500

代码