Hill Driving (UVa Live Archive Europe Northwestern 2010)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=397&page=show_problem&problem=2948

問題

制限速度がvmaxの山道を通ってなるべく速く家に帰りたい。ただし燃料が少ないのでそれを考慮に入れなければならない。スロープをsi(=xi/yi)とすると、燃料は1キロメートルあたり分減る。現在残っている燃料fを与えるので家まで何時間で着くか求めよ。
0.1<=α,β<=100
10<=vmax<=200
0<=f<=50
1<=スロープの数<=10000
1<=xi<=1000
-1000<=yi<=1000

解法

-βs/α