eolymp
bolt
Try our new interface for solving problems
Məsələlər

Столкновения

Столкновения

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

На прямой расположены одинаковые шарики, которые могут двигаться только вдоль этой прямой. Изначально каждый шарик движется с постоянной скоротью (знак скорости задаёт направление). После столкновения шарика A, двигающегося со скоростью V_A и шарика B, двигающегося со скоростью V_B шарик B начинает двигаться со скоростью V_A, а шарик A - со скоростью V_B. Вычислите общее количество произошедших при этом столкновений.

Giriş verilənləri

В первой строке входного файла задано количество шариков N (3N200000). Каждая из последующих N строк содержит 2 целых числа - начальную координату и соответствующую скорость. Все стартовые координаты находятся в диапазоне –10^11 < x_i < 10^11, все скорости в диапазоне –10^8 < v_i < 10^8. Для любых двух шариков стартовые координаты различны; также гарантируется отсутствие "тройных" и более столкновений.

Çıxış verilənləri

Выведите одно число - общее количество столкновений или 987654321987654321, если количество столкновений бесконечно.

Nümunə

Giriş verilənləri #1
3
-5 3
0 -1
7 -2
Çıxış verilənləri #1
3