농부 존이 기르는 소 N마리(1≤N≤50000)가 농장 앞 도로를 우르르 달려간다. 사실은 어느 소가 가장 빠른지 겨루는 달리기 경주다.
위에서 내려다보면 소 한 마리는 길이가 1인 수평 선분이고, t=0에서의 왼쪽 끝점 좌표로 위치를 나타낸다. 예를 들어 (−3,6)은 t=0에 (−3,6)에서 (−2,6)까지 이어지는 선분인 소다. 모든 소는 오른쪽(+x 방향)으로 달리고, 속도는 오른쪽으로 1만큼 가는 데 걸리는 시간을 정수로 준다.
존은 소가 외양간에서 우유를 만들지 않고 밖에서 달리는 것이 못마땅해서, 경주가 끝나면 따끔하게 훈계하려고 한다. 어느 소가 경주에 참가했는지 알아내려고 존은 (0,0)에 서서 +y 방향으로 뻗은 반직선을 바라본다. 경주가 진행되는 동안 한 번이라도 이 반직선에서 가장 먼저 보이는 소가 되면, 존은 그 소를 본 것이다. 어떤 소는 존의 시선을 지나는 동안 계속 다른 소가 앞에 있어서 보이지 않을 수 있다.
경주 내내 존이 볼 수 있는 소가 몇 마리인지 구하라.
첫째 줄에 N이 주어진다.
다음 N개 줄에 소 한 마리를 나타내는 정수 x, y, r이 공백으로 구분되어 주어진다. 그 소는 t=0에 왼쪽 끝점이 (x,y)이고, 시간 r마다 거리 1씩 일정한 속도로 오른쪽으로 이동한다. x는 −1000≤x≤−1, y는 1≤y≤1000000이며, 충돌이 생기지 않도록 모든 소의 y는 서로 다르다. r은 1≤r≤1000000이다.
t=0부터 경주가 끝날 때까지 존이 볼 수 있는 소의 수를 정수 하나로 출력한다.
시간은 t=0 이후로 연속해서 흐른다. 어떤 소가 반직선 x=0 위에 있는 시각 가운데 자기보다 y가 작은 소가 같은 시각에 그 반직선 위에 없는 시각이 하나라도 있으면, 존은 그 소를 본다.
소의 선분은 양 끝점을 포함한다. 따라서 오른쪽 끝점이 x=0에 닿는 순간부터 왼쪽 끝점이 x=0을 지나는 순간까지가 그 소가 존의 시선 위에 있는 시간이다.