Stampede#11189
Farmer John's cows appear to be stampeding along the road in front of FJ's farm, but in reality, they are simply competing in a foot race to determine which cow is the fastest.
Viewed from above, each cow is represented by a horizontal line segment of length . The position of a cow is specified by the coordinates of the left endpoint of this segment at time t = 0. For example, represents a cow whose segment extends from to at time t = 0.
Each cow moves to the right, in the direction, at a constant speed. Her speed is specified by the integer , which represents the amount of time required for the cow to travel unit of distance to the right.
FJ is not particularly happy that his cows are outside racing instead of staying in the barn and producing milk. He plans to give them a stern lecture after the race. To determine which of his cows are participating in the race, FJ stands at and looks along the ray extending in the direction.
As the race unfolds, FJ sees a cow if, at some point in time, she is the first cow visible along this ray. In other words, a cow may never be visible if another cow is always "in front" of her throughout the entire time she crosses FJ's line of sight.
Please determine the number of cows FJ can see at some point during the race.
The first line contains an integer n~(1 \le n \le 50000).
Each of the following lines describes a cow using three integers , and . The cow's left endpoint is at at time t = 0, and she moves to the right at a constant speed of unit of distance every units of time.
The value of is in the range -1000 \ldots -1, the value of is in the range 1 \ldots 10^6 (and is distinct for every cow, to prevent any possible collisions), and the value of is in the range 1 \ldots 10^6.
Print one integer specifying the number of cows FJ can see at some point during the race, starting from t = 0.
FJ can see cows and , but not cow .
Example 1