레이팅 미적용농부 존의 소 N마리가 (1 <= N <= 50,000) 달리기 경주를 하고 있다. 위에서 내려다보면 각 소는 길이 1의 수평 선분이며, 시각 t=0에서의 왼쪽 끝점 좌표로 주어진다. 각 소는 오른쪽 (+x 방향)으로 이동하며, 오른쪽으로 1 단위 이동하는 데 걸리는 정수 시간이 주어진다.
농부 존(FJ)은 (0,0)에 자리를 잡고 +y 방향으로 뻗은 반직선을 따라 바라본다. 경주가 진행되는 동안, 어떤 소가 한 순간이라도 이 반직선 위에서 가장 앞에 보이는 소가 된다면 FJ는 그 소를 본 것이다. 어떤 소가 FJ의 시선을 가로지르는 내내 다른 소가 그 "앞"에 있으면 그 소는 보이지 않을 수 있다.
경주 전체 동안 FJ가 볼 수 있는 소의 수를 계산하시오.
첫째 줄에 N이 주어진다.
다음 N개의 줄 각각에는 소 한 마리를 나타내는 세 정수 x y r이 주어진다: 시각 t=0에 왼쪽 끝점이 (x,y)에 있고, r 단위 시간마다 1 단위씩 오른쪽으로 이동한다. x는 -1000..-1, y는 1..1,000,000 범위이고 (모든 소마다 서로 다름), r은 1..1,000,000 범위이다.
경주 전체 동안 (t=0부터) FJ가 볼 수 있는 소의 수를 나타내는 정수 하나를 출력한다.
stampede.in · 출력을 쓸 파일 stampede.out3
-2 1 3
-3 2 3
-5 100 12Output details: FJ can see cows 1 and 2 but not cow 3.
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > January > Silver