Rivers
TopCoder SRM 543
Time Limit: 0.4s, Memory Limit: 64MiB
Пазаруването определено не е лесна задача. Да, разбира се, ако искате да си купите маратонки или някакви други парцалки, със сигурност няма да имате големи проблеми. Какво става, обаче, ако искате да се сдобиете с ужасно рядка отрова, срещаща се само по крайбрежието на Амазонка? Виждате, животът на Ели не е толкова лесен, колкото си мислите.

Момичето почти е достигнало своята крайна дестинация (река Амазонка, кръстена на сайта Amazon.com). За нещастие, последния участък може да бъде преминат само пътувайки с лодка и пеша.

Там има N+1 много дълги, но тесни паралелни острова, разположени от юг на север по дължина. За простота сме ги номерирали с числата от 1 до N+1, включително. Между всеки два съседни острова има река (тоест общо N реки), които пък са номерирани от 1 до N. Река i тече между острови i и i+1 и има широчина Wi километра. Максималната скорост, с която Ели може да се движи в тази река пък е Si километра в час. Водата в реките се движи толкова бавно, че нейната скорост може да бъде пренебрегната.

Всички острови имат дължина L километра. Започвайки от най-южната точка на всеки от тях, през един километър има док с лодки, от който Ели може да се сдобие с такава. Тоест, на всеки от островите има L+1 дока, разположение на нулевия, първия, … и L-тия километър на острова. Островите са толкова тесни, че можете да считате, че един и същи док обслужва и двете страни на острова (източната и западната), като времето за стигане от една от тях до другата е пренебрежимо малко.

Rivers Example За простота ще представим островите като паралелни вертикални отсечки, а доковете – като точки. Остров 1 започва от (0, 0) и се простира до (0, L); остров 2 започва от (W1, 0) и завършва в (W1, L); остров 3 започва в (W1 + W2, 0) и завършва в (W1 + W2, L); и така нататък. Доковете на остров 1 са с координати (0, 0), (0, 1), …, (0, L); тези на остров 2 са с координати (W1, 0), (W1, 1), …, (W1, L); тези на остров 3 са с координати (W1 + W2, 0), (W1 + W2, 1), …, (W1 + W2, L); и така нататък.

Ели може два вземе лодка от док до док. Забележете, че когато използва лодка, тя трябва както да я вземе от док, така и да акостира в такъв – тоест може да пътува с лодка само между точки с цели координати на съседни острови. Също така тя може да върви пеша (вертикално) със скорост G километра в час по всеки от островите.

Момичето в момента се намира в най-южната част на най-западния остров и иска да стигне най-северната част на най-източния такъв. Тя се чуди какво е минималното време, за което може да стигне до там.
Вход
На първия ред на стандартния вход са зададени целите числа N, L и G – съответно броя реки, дължината на всеки остров и скоростта, с която Ели ходи пеша по островите. Следват N реда с двойки числа Wi и Si – съответно ширината на i-тата река и скоростта, с която може да се движи Ели в нея.
Изход
На стандартния изход изведете едно число с плаваща запетая – минималното време, за което Ели може да стигне до своята дестинация. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9.
Ограничения
  • 1 ≤ N ≤ 50
  • 1 ≤ L ≤ 100,000
  • 1 ≤ G, Wi, Si ≤ 1,000,000
Примерен Вход Примерен Изход
3 10 3 5 5 2 2 3 7 3.231651964066
15 7134 1525 11567 1620 19763 1477 11026 2837 10444 2590 24588 1692 22263 2270 17709 1655 11181 1078 15292 2683 28895 1475 15039 1383 18744 1153 19985 1862 13795 1770 26697 1671 160.8289997
В първия пример Ели няма да ходи пеша по никой от островите. Вместо това, тя ще плава четири километра на север в първата река, достигайки втория остров в точка (5, 4). След това тя плава още един километър на север във втората река, достигайки третия остров в точка (7, 5). В последната река момичето плава директно към крайната дестинация – точката с координати (10, 10). Пътят й е показан на картинката в условието.
Времената за пътуване по време на нейното пътешествие са, съответно:
(0, 0) -> (5, 4) = 6.403124237433 / 5 = 1.280624847487
(5, 4) -> (7, 5) = 2.236067977499 / 2 = 1.118033988749
(7, 5) -> (10, 10) = 5.830951894845 / 7 = 0.83299312783
Мрън!