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

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

공원 산책

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

요약
주어진 수평 또는 수직 경로에서 보이는 나무의 수를 구한다. 나무와 경로 사이에 다른 나무가 없으면 보이는 것으로 본다.
난이도

보통10점 중 7점

유형
정렬, 해시맵, 시뮬레이션, 기하
정답자
아직 제출이 없습니다

문제

공원의 나무들이 건강하게 자라도록 점검하는 일을 맡았습니다. 각 나무의 위치는 2차원 평면 위의 정수 좌표 점으로 주어집니다. 잔디를 최근에 새로 심었기 때문에, 여러 개의 산책로 위에서만 이동할 수 있습니다. 각 산책로는 평면 위의 무한히 긴 수평선 또는 수직선입니다.

산책로에서 몇 그루의 나무를 볼 수 있는지 알고 싶습니다. 나무는 산책로 위의 어떤 지점에 서서 그 산책로와 수직인 방향을 바라볼 때에만 볼 수 있습니다. 즉, 수직 산책로에서는 수평 방향을, 수평 산책로에서는 수직 방향을 바라봅니다. 그 방향을 바라볼 때 나와 대상 나무 사이에 다른 나무가 하나도 없으면 그 나무가 보입니다.

적어도 하나의 산책로에서 보이는 나무의 수를 구하세요.

입력

입력은 하나의 공원 구성을 다음 형식으로 나타냅니다.

NTREES NPATHS
X(1) Y(1)
.
.
.
X(NTREES) Y(NTREES)
PATH(1)
.
.
.
PATH(NPATHS)

NTREES와 NPATHS는 [1,100000][1, 100000] 범위의 정수입니다. 이어지는 NTREES개의 줄에는 각 나무의 정수 좌표가 주어집니다. 그 다음 NPATHS개의 줄에는 각각 x=C 또는 y=C 형식으로 수직 또는 수평 산책로가 주어지며, C는 [−1000000,1000000][-1000000, 1000000] 범위의 정수입니다.

모든 좌표는 [−1000000,1000000][-1000000, 1000000] 범위에 있습니다. 모든 나무는 서로 다르고, 어떤 나무도 산책로 위에 있지 않으며, 모든 산책로는 서로 다릅니다.

출력

적어도 하나의 산책로에서 보이는 나무의 수를 정수 하나로 출력합니다.

예제3

  1. 예제 1

    입력
    6 3
    -1 3
    4 2
    6 2
    6 3
    6 4
    4 3
    x=0
    y=-1
    y=5
    
    예상 출력
    5
    
  2. 예제 2

    입력
    1 1
    0 0
    x=3
    
    예상 출력
    1
    
  3. 예제 3

    입력
    2 1
    0 0
    10 0
    x=5
    
    예상 출력
    2