만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

거실의 왕도마뱀

시간 제한5초메모리 제한512 MB

요약
TV 좌표와 N마리 도마뱀의 위치 및 키가 주어질 때, 각 도마뱀이 TV까지의 선분 위에 있는 모든 도마뱀보다 키가 크도록 남길 수 있는 최대 마릿수를 구한다.
난이도

보통10점 중 7점

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

문제

왕도마뱀은 냉혈성과 컴퓨터 화면 중독으로 유명한 파충류다. 영어 이름이 monitor lizard인 만큼 화면을 좋아해서, 하루 대부분을 거실의 작은 텔레비전 앞에 붙어서 보낸다.

한 파충류관에서 문제가 생겼다. 모여든 도마뱀이 너무 많아 이제는 모두가 화면을 볼 수 없다. 도마뱀은 자기 자리에서 텔레비전까지 이은 선분 위에 앉은 모든 도마뱀보다 키가 엄격하게 클 때만 화면을 본다.

도마뱀은 화면에 무엇이 나오는지, 비스듬히 보는지 정면으로 보는지 따지지 않는다. 화면이 시야에 들어오기만 하면 된다.

대신 자리는 옮기지 않는다. 뒤에 앉은 도마뱀이 보도록 어떤 도마뱀을 방 밖으로 내보내거나 그대로 둘 수 있지만, 방 안의 다른 자리로 옮기는 것은 불가능하다.

도마뱀을 최적으로 내보낼 때, 최대 몇 마리가 남아서 화면을 볼 수 있는가?

입력

  • 첫째 줄에 텔레비전의 좌표를 나타내는 정수 TXTX와 TYTY가 공백으로 구분되어 주어진다 (−106≤TX,TY≤106-10^6 \le TX, TY \le 10^6).
  • 둘째 줄에 도마뱀의 수를 나타내는 정수 NN이 주어진다 (1≤N≤1061 \le N \le 10^6).
  • 다음 NN개 줄에 도마뱀 한 마리의 좌표와 키를 나타내는 정수 XiX_i, YiY_i, HiH_i가 공백으로 구분되어 주어진다 (−106≤Xi,Yi≤106-10^6 \le X_i, Y_i \le 10^6, 1≤Hi≤1061 \le H_i \le 10^6).

텔레비전과 도마뱀 NN마리의 좌표는 모두 서로 다르다.

출력

화면을 동시에 볼 수 있는 도마뱀 수의 최댓값을 출력한다.

예제3

  1. 예제 1

    입력
    50 50
    2
    60 50 1
    65 50 2
    
    예상 출력
    2
    
  2. 예제 2

    입력
    50 50
    3
    60 55 1
    70 60 1
    40 45 1
    
    예상 출력
    2
    
  3. 예제 3

    입력
    -100 0
    6
    -99 1 2
    -98 2 4
    -97 3 3
    -96 4 4
    0 100 3
    100 0 7
    
    예상 출력
    4