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

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

Там има четири много дълги, но тесни паралелни острова, разположени от юг на север по дължина. За простота сме ги номерирали с числата от 1 до 4, включително. Между всеки два съседни острова има река, които пък са номерирани от 1 до 3. Река i тече между острови i и i+1 и има широчина Wi километра. Three Rivers Example

За простота ще представим островите като паралелни вертикални отсечки в равнината. Всички острови имат еднаква дължина L. Първият остров започва от (0, 0) и се простира до (0, L); втрорият започва от (W1, 0) и завършва в (W1, L); третият започва в (W1 + W2, 0) и завършва в (W1 + W2, L), а последният от (W1 + W2 + W3, 0) до (W1 + W2 + W3, L).

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

Момичето в момента се намира в най-южната част на най-западния остров и иска да стигне най-северната част на най-източния такъв. Тя се чуди какво е минималното време, за което може да стигне до там.
Вход
На първия ред на стандартния вход са зададени целите числа L и G – съответно дължината на островите и скоростта, с която Ели може да се движи пеша по тях. Следващите три реда ще съдържат по двойка числа Wi и Si – съответно ширината на i-тата река и скоростта, с която може да се движи Ели в нея.
Изход
На стандартния изход изведете едно число с плаваща запетая – минималното време, за което Ели може да стигне до своята дестинация. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9.
Ограничения
  • 1 ≤ L, Wi ≤ 1000
  • 1 ≤ G, Si ≤ 100
Примерен Вход Примерен Изход
10 8 5 5 2 2 3 7 3.206351837
1000 100 91 28 911 97 85 19 21.5493216136
873 54 444 67 588 97 263 26 26.36554002321
В първия пример един оптимален път би бил да се вземе сал от (0, 0) до (5, 4.003203734135), след това ходейки по втория остров да се достигне (5, 4.050839751462), след което да се построи нов сал, с който да се стигне до (7, 4.567237538143) на третия остров. От там, без ходене директно се взима нов сал до (10, 9.989414218372), а последната отсечка до (10, 10) се изминава пеша.
Нужните времена са, съответно:
(0, 0) -> (5, 4.003203734135) = 6.405126082833 / 5 = 1.281025216567
(5, 4.003203734135) -> (5, 4.050839751462) = 0.047636017327 / 8 = 0.005954502166
(5, 4.050839751462) -> (7, 4.567237538143) = 2.065591119774 / 2 = 1.032795559887
(7, 4.567237538143) -> (10, 9.989414218372) = 6.196773350028 / 7 = 0.885253335718
(10, 9.989414218372) -> (10, 10.000000000000) = 0.010585781628 / 8 = 0.001323222703
Мрън!