공원

면접 대비

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

요약

경로에서 수직 방향으로 바라볼 때 다른 나무에 가려지지 않는 나무의 개수를 구합니다.

난이도: 보통10점 중 4점
유형: 해시맵, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

나는 나무를 바라보는 것을 좋아한다. 공원에는 나무가 많아서 깨어 있는 시간의 대부분을 공원에서 보낸다. 심각한 시력 문제가 있어서 나무를 제대로 보기 어렵다. 공원에는 걸을 수 있는 길이 여러 개 있다. 각 길은 평면에서 수평 또는 수직으로 무한히 뻗은 직선이다. 어떤 나무도 길 위에 있지 않다. 모든 나무의 위치와 모든 길이 주어졌을 때, 공원에서 볼 수 있는 나무의 수를 구하라.

시력 문제 때문에 나무는 어떤 길 위에 서서 그 길과 수직인 방향을 바라볼 때만 보인다. 나무는 모두 너비가 같으므로, 내가 서 있는 곳과 나무 사이에 다른 나무가 있으면 뒤에 있는 나무는 보이지 않는다.

입력

첫 줄에는 이어지는 데이터 세트의 수를 나타내는 정수가 주어진다. 각 데이터 세트는 여러 줄로 이루어진다. 첫 줄에는 나무의 수 $n$ 과 길의 수 $m$ 이 정수로 주어진다. 다음 $n$ 줄에는 나무의 좌표 $x$ , $y$ 가 정수로 주어진다. 이어지는 $m$ 줄에는 $x=a$ 또는 $y=a$ 형태의 직선 방정식이 주어진다.

출력

볼 수 있는 나무의 수를 출력한다.

예제1

예제 1

입력

2
6 3
-1 3
4 2
6 2
6 3
6 4
4 3
x=0
y=-1
y=5
1 2
2 3
x=5
y=5

예상 출력

5
1