문제
누군가 서준이의 G(1≤G≤105)개의 정원에 있는 모든 풀을 뜯어먹었다!
화가 난 서준이는 뛰어난 수사 능력으로 범죄 현장에서 언제 풀이 뜯겼는지 정확한 시간을 알아냈다.
또한 G개의 정원 모두 한 소에 의해 뜯겼다는 정보를 얻어냈다.
서준이는 N(1≤N≤105)마리 소들을 집합시켜 조사를 하기 시작했다.
억울한 소들은 각자의 자기가 안했다며 결백을 증명하기 위해 특정 시간에 특정 위치에 있었다는 점을 서준이에게 알려줬다.
서준이를 도와 몇 마리의 소들이 결백한지 검증하는 프로그램을 작성하자.
소들은 1 단위 시간당 1 단위 거리만큼 움직일 수 있다.
입력
첫 번째 줄에 G와 N이 공백을 구분으로 주어진다.
그 다음 G개의 줄에 걸쳐 정원의 위치와 풀이 뜯긴 시간인 x, y, t (−109 ≤ x,y ≤ 109; 0 ≤ t ≤ 109)가 공백을 구분으로 주어진다.
(항상 한 소가 모든 정원을 방문할 수 있다는게 보장된다.)
그 다음 N개의 줄에 걸쳐 소의 위치와 소가 있었던 시간인 x,y,t (−109 ≤ x,y ≤ 109; 0 ≤ t ≤ 109)가 공백을 구분으로 주어진다.
출력
결백을 증명할 수 있는 소들의 수를 출력한다.
예제
2 4
0 0 100
50 0 200
0 50 50
1000 1000 0
50 0 200
10 0 170
2
힌트
출처
USACO 2023 February Silver
로그인해야 코드를 작성할 수 있어요.