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

Гонки

Гонки

n коров Фермера Джона стоят вдоль дороги перед фермой - предстоит забег, чтобы узнать какая корова самая быстрая.

Каждая корова представлена горизонтальным отрезком одиночной длины, с началом в левой угловой точке в момент времени t = 0. Например, (-3, 6) обозначает корову, которая в момент времени 0 представлена отрезком из (-3, 6) в (-2, 6). Каждая корова движется вправо (в направлении + по оси x), на некоторой скорости указанной количеством времени, требуемым для того, чтобы переместиться на единицу расстояния вправо.

ФД для того, чтобы определить, какие из его коров участвуют в гонке, расположился в точке (0, 0) и смотрит в направлении +y. ФД видит только ближайшую к себе корову. То есть корова может быть не видима, если другая корова находится «перед ней» всё время пока пересекает «линию взгляда» ФД.

Определите количество коров, которые ФД увидит во время гонок.

Входные данные

Первая строка ввода содержит n (1n50000). Каждая из последующих n строк описывает одну корову тремя целыми числами x y r, определяющими левую точку коровы (x, y) в момент времени t = 0 и постоянную скорость её движения вправо r, то есть что эта корова перемещается на 1 единицу расстояния за r единиц времени. x находится в диапазоне -1000..1, а y находится в диапазоне 1..106 (и различается для каждой коровы, чтобы предотвратить коллизии), значение r находится в диапазоне 1..106.

Выходные данные

Выведите количество коров, которых ФД сможет увидеть за время гонки от момента времени 0 и далее.

Пример

ФД сможет увидеть коров 1 и 2 и не сможет увидеть корову 3.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3
-2 1 3
-3 2 3
-5 100 1
Çıxış verilənləri #1
2
Mənbə 2015 USACO Январь, Серебро