만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

강입자 충돌기

시간 제한2초메모리 제한1024 MB

요약
서로 겹치지 않는 원 최대 세 개가 주어질 때, 각 원을 지름의 양 끝에서 만나 정확히 반으로 나누는 원을 찾는다.
난이도

어려움10점 중 8점

유형
기하, 수학, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

두 나라 바이트란디아와 플랫란디아는 고에너지 물리학 연구에서 힘을 합치기로 하고 nn개의 강입자 충돌기를 건설했다. 각 충돌기는 링 모양이며 지하에 있다. 각 충돌기의 두께는 무시할 수 있으므로 원으로 생각할 수 있다.

강입자 충돌기는 다루기 까다롭고 항상 주의를 기울여야 하는 장치이다. 어느 나라도 모든 충돌기의 유지 보수를 혼자 맡으려 하지 않았기 때문에 유지 보수를 두 나라가 나누기로 했다. 공정하게 하기 위해 각 나라는 모든 충돌기의 절반씩을 유지 보수하기로 했다. 책임 구역의 경계는 원으로 긋기로 했다. 따라서 각 충돌기를 길이가 같은 두 부분으로 나누는 원, 즉 각 충돌기와 지름 방향으로 마주 보는 두 점에서 만나는 원을 찾아야 한다.

건설한 충돌기의 설명이 주어지면 조건을 만족하는 원을 찾는 프로그램을 작성해야 한다.

입력

입력 파일의 첫째 줄에는 정수 nn이 주어진다(1≤n≤31 \le n \le 3). 다음 nn개의 줄에는 각각 충돌기 하나의 설명이 주어진다. 충돌기의 설명은 세 정수 xx, yy, rr로 이루어진다. 이는 충돌기 중심의 좌표와 반지름이다(∣x∣,∣y∣≤1000|x|, |y| \le 1000, 1≤r≤10001 \le r \le 1000). 충돌기들은 서로 만나는 점이 없고, 하나가 다른 하나 안에 들어 있지 않으며, n=3n=3일 때 중심들은 한 직선 위에 있지 않다.

출력

출력 파일의 첫째 줄에 찾은 경계의 설명을 출력한다. 즉 원의 중심 좌표와 반지름을 출력한다. 소수점 이하 자리를 최대한 많이 출력한다. 답을 검사할 때 10−510^{-5}를 넘지 않는 오차는 무시한다.

원의 중심 좌표와 반지름의 절댓값은 10710^7을 넘지 않아야 한다. 주어진 제한을 만족하는 답이 존재함이 보장된다.

예제2

  1. 예제 1

    입력
    2
    2 0 1
    -2 0 1
    
    예상 출력
    0 0 2.2360679774997897
    
  2. 예제 2

    입력
    3
    0 10 1
    0 0 2
    10 10 3
    
    예상 출력
    5.4 4.85 7.52877812