a354: WC2007 2.疯狂赛车
標籤 :
通過比率 : 88% (7 人 / 8 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2014-11-01 02:15

內容

布布是一个《泡泡堂》高手,拥有着近乎完美的战绩。他擅长很多地图,例如“小区10”、“海盗14”、“大海02”等等,不过他最喜欢的地图是“赛车”。

 

在赛车地图中,每个玩家将得到一辆赛车,从起点出发,比赛谁最先到达终点。

 

在地图中,包括有障碍、加油站、赛车跑道与沙地。障碍不可通过,并且赛车在赛车跑道与沙地上的行进速度是不一样的。

 

现在我们来考虑一个简化版的赛车游戏。在这个简化版本的赛车游戏中:

l        比赛在一个无限大的沙地平面上举行。

l        赛道是一个从原点出发、由n条线段首尾相接组成的折线。

l        出于安全考虑,赛道不会自交(即折线中的任何两条线段,相邻两条线段有且仅有一个公共点,其他任意两条线段均无公共点)。

l        赛车在赛道上的速度为va,在沙地上的速度为vb,且满足

l        为了增加比赛的挑战性,在赛道上逆向行驶是允许的。

 

布布是一个操作非常精确的选手,他总能按照预想的道路行进至终点,但是他不知道哪个才是最快的路线,聪明的你,能帮助他么?

輸入說明

输入的第1行包含一个整数n,表示赛道一共有n段;第2行包含两个实数vavb,分别表示赛车在赛道上与沙地中的行进速度。接下来的n行,每行包含两个整数xiyi,依次表示赛道的每一个转折点。即赛道的第一个线段是(0,0)à(x1 , y1),第二条线段是(x1 , y1)à ( x2 , y2),依次类推。其中(xn , yn)为终点。

輸出說明
输出仅包含一个实数,表示从起点到终点最少所需时间。精确到小数点后6位。
範例輸入
2
2 1
0 4
4 4

2
2 1
4 4
4 -4
範例輸出
4.000000

5.464102
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 3.0s , <1K
公開 測資點#1 (10%): 3.0s , <1K
公開 測資點#2 (10%): 3.0s , <1K
公開 測資點#3 (10%): 3.0s , <1K
公開 測資點#4 (10%): 3.0s , <1M
公開 測資點#5 (10%): 3.0s , <1M
公開 測資點#6 (10%): 3.0s , <1M
公開 測資點#7 (10%): 3.0s , <1M
公開 測資點#8 (10%): 3.0s , <1M
公開 測資點#9 (10%): 3.0s , <1M
提示 :
对于20%的数据,赛道的折线段平行于坐标轴。
对于40%的数据,n<=50
对于100%的数据,n<=1000,1<=Vb<=Va<=20
所有的坐标都在[-106 , 106]内。

標籤:
出處:
WC2007第二题 [編輯:
liouzhou_101 (王启圣)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」