Столкновения
Столкновения
На прямой расположены одинаковые шарики, которые могут двигаться только вдоль этой прямой. Изначально каждый шарик движется с постоянной скоротью (знак скорости задаёт направление). После столкновения шарика A, двигающегося со скоростью V_A и шарика B, двигающегося со скоростью V_B шарик B начинает двигаться со скоростью V_A, а шарик A - со скоростью V_B. Вычислите общее количество произошедших при этом столкновений.
Giriş verilənləri
В первой строке входного файла задано количество шариков N (3 ≤ N ≤ 200000). Каждая из последующих N строк содержит 2 целых числа - начальную координату и соответствующую скорость. Все стартовые координаты находятся в диапазоне –10^11 < x_i < 10^11, все скорости в диапазоне –10^8 < v_i < 10^8. Для любых двух шариков стартовые координаты различны; также гарантируется отсутствие "тройных" и более столкновений.
Çıxış verilənləri
Выведите одно число - общее количество столкновений или 987654321987654321, если количество столкновений бесконечно.
Nümunə
3 -5 3 0 -1 7 -2
3