이 문제는 스위스 치즈 모델 (Hard)와 문제 제목의 Easy/Hard 표기 및 붉게 표시된 부분만 다르다. 그러나 Hard와 Easy의 풀이법이 다르기 때문에 Hard의 풀이로 Easy까지 해결할 수 없음에 유의하라.
위험 관리 분석 모형 중에 스위스 치즈 모델이라는 이론이 있다. 여러 겹의 안전 체계가 있다고 하더라도 각각의 안전 체계에는 약점이 있으며 이 약점들이 우연히 이어지면 사고가 끝까지 통과할 수 있다는 이야기이다.
당신은 이 모델을 여러 장의 치즈를 이용해 단순화하여 분석해 보기로 했다. 모든 치즈는 두께가 이고, 축과 축 방향으로 무한히 넓은 평평한 판이라고 가정한다. 치즈에는 앞에서부터 번부터 번까지 번호가 붙어 있다. 번 치즈의 앞면은 평면 , 뒷면은 평면 에 놓인다. 따라서 모든 치즈의 앞면과 뒷면은 -평면과 평행하며, 이웃한 치즈는 빈틈없이 면을 맞대고 있다.
첫째 줄에 치즈의 수 이 주어진다.
이후 번부터 번까지의 치즈 정보가 순서대로 주어진다. 각 치즈 정보의 첫째 줄에는 그 치즈에 뚫린 구멍의 수 가 주어진다. 이어지는 개의 줄에는 정수 , , 이 공백으로 구분되어 주어진다. 이는 -평면과 평행한 단면이 중심 , 반지름 인 원판인 구멍을 의미한다.
사고가 모든 치즈를 통과할 수 없으면, 즉 치즈 배치가 안전하면 YES를 출력한다. 그렇지 않으면 NO를 출력한다.
첫 번째 예제에서는 평면 좌표 가 세 치즈의 구멍 단면에 모두 포함된다. 따라서 에서 까지 축과 평행하게 이동하면 모든 치즈를 통과할 수 있고, 답은 이다.
각 치즈에는 앞면에서 뒷면까지 관통하는 원기둥 모양의 구멍이 하나 이상 뚫려 있다. 모든 구멍의 축은 축과 평행하다. 따라서 한 구멍을 -평면과 평행하게 자른 단면은 깊이에 관계없이 중심의 좌표와 반지름이 같은 원판이다. 모든 치즈는 하나의 공통 좌표계를 사용한다.
사고는 크기가 없는 점의 이동으로 생각한다. 이동하는 동안에는 항상 어느 치즈의 구멍 안이나 구멍의 경계 위에 있어야 한다.
사고의 경로는 구멍 안에서 자유롭게 방향을 바꾸며 이동할 수 있다. 같은 치즈에 있는 두 구멍의 단면이 한 점이라도 공유하면 두 구멍 사이를 이동할 수 있다. 또한 이웃한 두 치즈의 맞닿은 면에서 두 구멍의 단면이 한 점이라도 공유하면 두 치즈 사이를 이동할 수 있다. 이때 앞쪽 치즈로 돌아가는 것도 허용한다.
첫 치즈의 앞면에 있는 어떤 구멍에서 출발하여 마지막 치즈의 뒷면에 있는 어떤 구멍까지 이동할 수 있다면 이 치즈 배치는 안전하지 않다.
주어진 치즈 배치에서 사고가 끝까지 통과할 수 없어 안전한지 판정하여라.
NO세 번째 예제에서는 두 구멍의 단면이 평면 좌표 에서 접한다. 구멍의 경계 위를 지나는 것도 허용되므로 에서 까지 이동할 수 있고, 따라서 답은 NO이다.
네 번째 예제에서는 2번 치즈 안에서 여러 구멍을 차례로 지나 오른쪽으로 이동할 수 있다. 따라서 1번 치즈와 3번 치즈의 구멍이 직접 만나지 않더라도 사고가 끝까지 이동할 수 있고, 답은 NO이다.