Park

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

요약

n개의 나무 좌표와 m개의 수평 또는 수직 경로가 주어질 때, 어떤 경로에서 수직 방향으로 볼 때 다른 나무에 가리지 않고 보이는 나무의 수를 센다.

난이도: 보통10점 중 4점
유형: 기하, 구현
정답자: 아직 제출이 없습니다

문제

You like looking at trees. A park has many trees. Therefore, you spend most of your waking hours at the park. You have an acute vision problem that severely limits your ability to look at these trees. The park has several paths that you can walk on. Each path is described by an infinite-length horizontal or vertical line in the 2D plane. No trees lie on a path. You want to know how many trees are visible in the park. Because of your vision problem, a tree is visible only if you can view it by standing on some path while facing in a direction perpendicular to that path. Of course all trees are equally wide, so if there is a second tree between the first tree and where you are currently standing, then you can’t see the first tree. Given location of all the trees and all the paths, determine how many trees you can view in the park.

입력

The first line in the data file is an integer that represents the number of data sets to follow. Each data set contains several lines. The first line contains two integers n and m, the number of trees and number of paths. The next n lines contains two integers x and y, which are the coordinates of the trees. The following m lines contains a line equation of the form x=a or y=a.

출력

Print the number of trees you can view.

예제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