페인트볼

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

요약
서쪽 변에서 동쪽 변으로 가로지르는 경로가 원형 사격 범위를 피해 지나갈 수 있는지 판정하고, 가능하면 가장 북쪽의 진입점과 진출점을 구한다.
난이도

보통10점 중 6점

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

문제

당신은 1000×10001000 \times 1000 크기의 정사각형 경기장에서 페인트볼 게임을 하고 있다. 여러 명의 상대가 경기장 곳곳의 나무 뒤에 숨어 있다. 각 상대는 자신이 있는 위치에서 어느 방향으로든 일정한 거리까지 페인트볼을 쏠 수 있다. 페인트볼에 맞지 않고 경기장을 가로질러 반대편까지 건너갈 수 있을까?

입력

경기장의 남서쪽 모서리는 (0,0)(0, 0), 북서쪽 모서리는 (0,1000)(0, 1000)에 있다고 하자. 첫째 줄에는 상대의 수 nn이 주어진다 (n≤1000n \le 1000). 이어지는 nn개의 줄에는 각 상대마다 세 개의 실수, 즉 상대의 위치 (x,y)(x, y)와 사정거리가 주어진다. 당신이 어느 순간이라도 어떤 상대의 사정거리 안으로 들어가면 그 상대의 페인트볼에 맞는다.

당신은 남서쪽 모서리와 북서쪽 모서리 사이(경기장의 서쪽 변)의 어딘가로 들어가서, 남동쪽 모서리와 북동쪽 모서리 사이(경기장의 동쪽 변)의 어딘가로 나와야 한다.

출력

경기장을 건널 수 있다면, 소수점 아래 둘째 자리까지의 실수 네 개를 공백으로 구분하여 출력한다. 순서대로 당신이 들어가는 지점의 좌표와 나오는 지점의 좌표이다. 들어가고 나올 수 있는 위치가 여러 곳이라면 가장 북쪽에 있는 것을 출력한다. 그런 위치의 쌍이 존재하지 않으면 다음 한 줄을 출력한다:

IMPOSSIBLE

예제2

  1. 예제 1

    입력
    3
    500 500 499
    0 0 999
    1000 1000 200
    
    예상 출력
    0.00 1000.00 1000.00 800.00
    
  2. 예제 2

    입력
    1
    500 500 600
    
    예상 출력
    IMPOSSIBLE