소 떼 질주

아직 제출이 없습니다시간 제한1초메모리 제한256 MB

문제

농부 존이 기르는 소 NN마리(1N500001 \le N \le 50000)가 농장 앞 도로를 우르르 달려간다. 사실은 어느 소가 가장 빠른지 겨루는 달리기 경주다.

위에서 내려다보면 소 한 마리는 길이가 1인 수평 선분이고, t=0t=0에서의 왼쪽 끝점 좌표로 위치를 나타낸다. 예를 들어 (3,6)(-3, 6)t=0t=0(3,6)(-3, 6)에서 (2,6)(-2, 6)까지 이어지는 선분인 소다. 모든 소는 오른쪽(+x+x 방향)으로 달리고, 속도는 오른쪽으로 1만큼 가는 데 걸리는 시간을 정수로 준다.

존은 소가 외양간에서 우유를 만들지 않고 밖에서 달리는 것이 못마땅해서, 경주가 끝나면 따끔하게 훈계하려고 한다. 어느 소가 경주에 참가했는지 알아내려고 존은 (0,0)(0, 0)에 서서 +y+y 방향으로 뻗은 반직선을 바라본다. 경주가 진행되는 동안 한 번이라도 이 반직선에서 가장 먼저 보이는 소가 되면, 존은 그 소를 본 것이다. 어떤 소는 존의 시선을 지나는 동안 계속 다른 소가 앞에 있어서 보이지 않을 수 있다.

경주 내내 존이 볼 수 있는 소가 몇 마리인지 구하라.

입력

첫째 줄에 NN이 주어진다.

다음 NN개 줄에 소 한 마리를 나타내는 정수 xx, yy, rr이 공백으로 구분되어 주어진다. 그 소는 t=0t=0에 왼쪽 끝점이 (x,y)(x, y)이고, 시간 rr마다 거리 1씩 일정한 속도로 오른쪽으로 이동한다. xx1000x1-1000 \le x \le -1, yy1y10000001 \le y \le 1000000이며, 충돌이 생기지 않도록 모든 소의 yy는 서로 다르다. rr1r10000001 \le r \le 1000000이다.

출력

t=0t=0부터 경주가 끝날 때까지 존이 볼 수 있는 소의 수를 정수 하나로 출력한다.

힌트

시간은 t=0t=0 이후로 연속해서 흐른다. 어떤 소가 반직선 x=0x=0 위에 있는 시각 가운데 자기보다 yy가 작은 소가 같은 시각에 그 반직선 위에 없는 시각이 하나라도 있으면, 존은 그 소를 본다.

소의 선분은 양 끝점을 포함한다. 따라서 오른쪽 끝점이 x=0x=0에 닿는 순간부터 왼쪽 끝점이 x=0x=0을 지나는 순간까지가 그 소가 존의 시선 위에 있는 시간이다.