n человек стоят на координатной прямой в точках с положительными целочисленными координатами, строго меньшими 106. Для каждого человека известно, в какую сторону он смотрит (влево или вправо), и его максимальная скорость.
У вас есть возможность разместить одну бомбу в точку с целочисленной неотрицательной координатой, и взорвать ее. В этот момент все люди побегут со своей максимальной скоростью в те стороны, в которые они смотрят, а от бомбы начнут распространяться два странных луча со скоростью s: влево и вправо. Конечно, скорость лучей s строго больше скорости любого человека.
Странность лучей в том, что в момент, когда положение некоторого луча и его направление совпадает с положением и направлением бега некоторого человека, скорость этого человека увеличивается на скорость луча.
Требуется положить бомбу в такое место, чтобы минимальный момент времени, в который и мимо точки 0, и мимо точки 106 пробежал хотя бы один человек, был как можно меньше. Иными словами, найдите минимальный момент времени t такой, что существует точка, в которую можно положить бомбу так, чтобы в момент времени t и мимо точки 0, и мимо точки 106 кто-то пробежал.
В первой строке находятся два целых числа n и s (2 ≤ n ≤ 105, 2 ≤ s ≤ 106) — количество человек на прямой и скорость лучей.
В следующих n строках находятся описания людей. В i-й из этих строк находятся три целых числа xi, vi и ti (0 < xi < 106, 1 ≤ vi < s, 1 ≤ ti ≤ 2) — координата i-го человека на прямой, его максимальная скорость и направление, в котором он побежит (1 — влево, т.е. в сторону уменьшения координаты, и 2 — вправо, т.е. в сторону увеличения координаты), соответственно.
Гарантируется, что точки 0 и 106 будут когда-либо достигнуты людьми независимо от положения бомбы.
Выведите минимальное время, за которое могут быть достигнуты обе точки 0 и 106.
Ваш ответ будет считаться правильным, если его абсолютная или относительная точность не превосходит 10 - 6. А именно, если ваш ответ равен a, а ответ жюри равен b, то ваш ответ будет зачтен, если 
.
2 999
400000 1 2
500000 1 1
500000.000000000000000000000000000000
2 1000
400000 500 1
600000 500 2
400.000000000000000000000000000000
В первом примере оптимально поставить бомбу в точке с координатой 400000. Тогда в момент времени 0 скорость первого станет 1000 и он достигнет точки 106 в момент времени 600. На второго человека бомба не повлияет и он достигнет точки 0 в момент времени 500000.
Во втором примере оптимально поставить бомбу в точке с координатой 500000. Лучи догонят обоих людей в момент времени 200. В этот момент первый находится в точке с координатой 300000, а второй 700000. Их скорость станет равна 1500 и в момент времени 400 они одновременно пересекут точки 0 и 106.
| Codeforces Round 425 (Div. 2) |
|---|
| Закончено |
