아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

뱀

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

요약
1000 x 1000 정사각형에서 각 뱀으로부터 거리 r 이상을 유지하며 서쪽 변에서 동쪽 변으로 가는 경로가 있는지 판정한다.
난이도

보통10점 중 6점

유형
기하, 유니온 파인드, 그래프
정답자
아직 제출이 없습니다

문제

버팔로 빌은 1000×10001000 \times 1000 크기의 정사각형 들판을 서쪽 변에서 동쪽 변까지 가로질러야 합니다. 들판 곳곳에는 여러 마리의 뱀이 있으며, 각 뱀은 자신의 위치에서 어느 방향으로든 정해진 거리만큼 공격할 수 있습니다. 빌이 어느 순간이라도 어떤 뱀에게 그 뱀의 공격 거리보다 더 가까이 다가가면 물립니다. 빌이 물리지 않고 들판을 가로지를 수 있는지 판정하세요.

입력

들판의 남서쪽 모서리는 (0,0)(0, 0), 북서쪽 모서리는 (0,1000)(0, 1000)에 있습니다. 따라서 서쪽 변은 직선 x=0x = 0, 동쪽 변은 직선 x=1000x = 1000이며, yy 좌표는 남쪽(00)에서 북쪽(10001000)으로 증가합니다. 빌은 서쪽 변 위의 한 점(x=0x = 0, 0≤y≤10000 \le y \le 1000)에서 들어와 동쪽 변 위의 한 점(x=1000x = 1000, 0≤y≤10000 \le y \le 1000)으로 나가야 합니다.

첫째 줄에 뱀의 수 nn (0≤n≤10000 \le n \le 1000)이 주어집니다. 이어지는 nn개의 줄에는 각각 세 실수 xx, yy, rr이 주어지며, 이는 뱀의 위치 (x,y)(x, y)와 공격 거리 rr을 나타냅니다. 모든 뱀은 들판 안(0≤x≤10000 \le x \le 1000, 0≤y≤10000 \le y \le 1000)에 있습니다. 뱀은 자신의 위치로부터 거리가 rr보다 작은 지점을 지나는 모든 것을 뭅니다. 거리가 정확히 rr인 지점은 안전합니다.

출력

빌이 어떤 뱀의 공격 거리 안에도 들어가지 않고 서쪽 변에서 동쪽 변까지 건널 수 있으면 Bill can make the trip.을 출력하세요. 그렇지 않으면 Bill will be bitten.을 출력하세요.

예제2

  1. 예제 1

    입력
    3
    500 500 499
    0 0 999
    1000 1000 200
    
    예상 출력
    Bill can make the trip.
    
  2. 예제 2

    입력
    3
    500 900 250
    500 500 250
    500 100 250
    
    예상 출력
    Bill will be bitten.