레이팅 미적용참고: 이 문제의 시간 제한은 기본의 두 배인 4초이다.
누군가가 농부 존의 개인 정원 \(G\) \((1 \le G \le 10^5)\)곳에서 풀을 뜯어 먹었다! 전문적인 법의학 지식을 활용하여 농부 존은 각 정원에서 풀이 뜯긴 정확한 시각을 알아냈다. 또한 모든 풀 뜯기 사건의 범인이 단 한 마리의 소라는 것도 알아냈다.
이 범죄에 대응하여, 농부 존의 소 \(N\) \((1 \le N \le 10^5)\)마리는 각각 특정 시각에 특정 위치에 있었음을 증명하는 알리바이를 제시했다. 각 알리바이가 그 소의 무죄를 입증하는지 검증하도록 농부 존을 도와준다.
어떤 소가 모든 풀 뜯기 사건 현장과 자신의 알리바이 사이를 모두 이동하는 것이 불가능하다면 그 소는 무죄로 판정할 수 있다. 소는 단위 시간당 1 단위 거리의 속도로 이동한다.
출제자: Mark Gordon
배점
- 입력 2-4: \(1 \le G, N \le 10^3\). 또한 정원과 알리바이 모두에 대해 \(-10^6 \le x, y \le 10^6\)이고 \(0 \le t \le 10^6\)이다.
- 입력 5-11: 추가 제약이 없다.
출제자: Mark Gordon
입력의 첫째 줄에 \(G\)와 \(N\)이 공백으로 구분되어 주어진다.
다음 \(G\)개의 줄에 풀 뜯기의 위치와 시각을 나타내는 정수 \(x\), \(y\), \(t\) \((-10^9 \le x, y \le 10^9; 0 \le t \le 10^9)\)가 공백으로 구분되어 주어진다. 한 마리의 소가 모든 풀 뜯기 현장 사이를 이동하는 것은 항상 가능하다.
다음 \(N\)개의 줄에 각 소의 알리바이의 위치와 시각을 나타내는 \(x\), \(y\), \(t\) \((-10^9 \le x, y \le 10^9; 0 \le t \le 10^9)\)가 공백으로 구분되어 주어진다.
무죄를 입증하는 알리바이를 가진 소의 수를 하나의 정수로 출력한다.
2 4
0 0 100
50 0 200
0 50 50
1000 1000 0
50 0 200
10 0 1702There were two grazings; the first at \((0, 0)\) at time \(100\) and the
second at \((50, 0)\) at time \(200\).
The first cow's alibi does not prove her innocence. She has just enough time to
arrive at the first grazing.
The second cow's alibi does prove her innocence. She is nowhere near any of the
grazings.
Unfortunately for the third cow, being at the scene of the crime does not prove
innocence.
Finally, the fourth cow is innocent because it's impossible to make it from her
alibi to the final grazing in time.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Silver