문제 설명
KoreaTech 나라에 벌레들이 대량으로 출몰 하였다고 합니다.
이 벌레들은 M x N 크기의 KoreaTech 나라의 영토 안 곳곳에 서식하고 있습니다. 그래서 이를 해결하기 위해, 종욱이와 찬효가 KoreaTech 나라로 파이어벳들을 파견하였습니다.
하지만 이 파이어벳들은 자기가 서 있는 자리를 기준으로 상하좌우 직선 상에 있는 모든 벌레들만 태워버릴수 있다고 합니다.
또한 파이어벳의 불꽃은 KoreaTech 나라 안 곳곳에 지어져있는 건물과 다른 파이어벳 너머로는 더이상 퍼지지 않는다고 합니다.
예를 들어 파이어벳이 북쪽으로 불을 쏘았을때 중간에 건물을 만나게 되면 더이상 불꽃은 북쪽으로 나아가지 못하고 건물 바로 앞까지 있는 모든 벌레들에 한해서만 불태울 수 있습니다.
영토에 파이어벳이 배치된 이후 불에 타지 않고 끝까지 생존한 벌레의 수를 구해주세요.
예시 1>
위와 같이 파이어벳과 건물들이 배치 되어있을 경우, 빨간색으로 채워진 칸을 제외한 5칸(마리)에 최종적으로 벌레들이 생존하게 됩니다.
예시 2>
위와 같이 파이어벳과 건물들이 배치 되어있을 경우, 빌딩 뒤에 숨어있는 벌레만 생존하게 됩니다. 따라서 1을 출력하면 됩니다.
이 벌레들은 M x N 크기의 KoreaTech 나라의 영토 안 곳곳에 서식하고 있습니다. 그래서 이를 해결하기 위해, 종욱이와 찬효가 KoreaTech 나라로 파이어벳들을 파견하였습니다.
하지만 이 파이어벳들은 자기가 서 있는 자리를 기준으로 상하좌우 직선 상에 있는 모든 벌레들만 태워버릴수 있다고 합니다.
또한 파이어벳의 불꽃은 KoreaTech 나라 안 곳곳에 지어져있는 건물과 다른 파이어벳 너머로는 더이상 퍼지지 않는다고 합니다.
예를 들어 파이어벳이 북쪽으로 불을 쏘았을때 중간에 건물을 만나게 되면 더이상 불꽃은 북쪽으로 나아가지 못하고 건물 바로 앞까지 있는 모든 벌레들에 한해서만 불태울 수 있습니다.
영토에 파이어벳이 배치된 이후 불에 타지 않고 끝까지 생존한 벌레의 수를 구해주세요.
예시 1>
위와 같이 파이어벳과 건물들이 배치 되어있을 경우, 빨간색으로 채워진 칸을 제외한 5칸(마리)에 최종적으로 벌레들이 생존하게 됩니다.
예시 2>
위와 같이 파이어벳과 건물들이 배치 되어있을 경우, 빌딩 뒤에 숨어있는 벌레만 생존하게 됩니다. 따라서 1을 출력하면 됩니다.
입력 설명
첫 줄에는 영토의 크기를 나타내는 M(1 ≤ M ≤ 105)과 N(1 ≤ N ≤ 105)이 주어집니다. 그 다음 줄에는 파이어뱃의 개수 F(1 ≤ F ≤ 5×104)가 주어지고, 그다음 F줄에 걸쳐 각 파이어뱃의 배치 위치를 나타내는 정수쌍 XF (0 ≤ XF < M)와 YF (0 ≤ YF < N)가 주어집니다.
그 다음 줄에는 건물의 개수 B(1 ≤ B ≤ 5 × 104)가 주어지고, 그 다음 B줄에 걸쳐 각 건물의 배치 위치를 나타내는 정수 쌍 XB(0 ≤ XB < M)와 YB(0 ≤ YB < N) 가 주어집니다. 주어진 각각의 파이어벳과 건물의 위치는 절대 겹치지 않습니다.
또 주어진 값들은 다음과 같은 조건을 추가로 만족합니다.
• 2 ≤ M × N ≤ 105
• 2 ≤ F + B ≤ M × N
그 다음 줄에는 건물의 개수 B(1 ≤ B ≤ 5 × 104)가 주어지고, 그 다음 B줄에 걸쳐 각 건물의 배치 위치를 나타내는 정수 쌍 XB(0 ≤ XB < M)와 YB(0 ≤ YB < N) 가 주어집니다. 주어진 각각의 파이어벳과 건물의 위치는 절대 겹치지 않습니다.
또 주어진 값들은 다음과 같은 조건을 추가로 만족합니다.
• 2 ≤ M × N ≤ 105
• 2 ≤ F + B ≤ M × N
출력 설명
박멸되지 않고 남은 벌레의 개수를 출력합니다.