아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

소 떼 질주

시간 제한1초메모리 제한256 MB

요약
y축 양의 방향을 가로지르는 동안 한 번이라도 가장 앞에 보이는 소를 셉니다.
난이도

보통10점 중 5점

유형
구간, 정렬, 그리디
정답자
아직 제출이 없습니다

문제

농부 존이 기르는 소 NN마리(1≤N≤500001 \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씩 일정한 속도로 오른쪽으로 이동한다. xx는 −1000≤x≤−1-1000 \le x \le -1, yy는 1≤y≤10000001 \le y \le 1000000이며, 충돌이 생기지 않도록 모든 소의 yy는 서로 다르다. rr은 1≤r≤10000001 \le r \le 1000000이다.

출력

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

힌트

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

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

예제2

  1. 예제 1

    입력
    3
    -2 1 3
    -3 2 3
    -5 100 1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    1
    -1 1 1
    
    예상 출력
    1