점과 원

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

요약
평면 위 서로 다른 네 점이 주어질 때, 네 점 각각까지의 거리가 모두 같은 원을 찾아 중심과 반지름을 출력한다. 그러한 원이 항상 존재함은 보장된다.
난이도

어려움10점 중 8점

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

문제

평면 위에 서로 다른 네 개의 점이 주어진다. 이들 네 점으로부터 모두 같은 거리에 있는 하나의 원을 찾고자 한다. 여기서 점과 원 사이의 거리는 원 위의 한 점에서 해당 점까지의 거리 중 가장 짧은 거리를 의미한다.

네 개의 점의 좌표가 주어질 때, 이러한 원의 중심 좌표와 반지름의 길이를 구하는 프로그램을 작성하시오. 모든 점이 일직선상에 존재하는 경우는 주어지지 않는다.

입력

네 줄에 걸쳐 각 점의 좌표를 이루는 두 개의 정수 xx, yy가 주어진다. (−100≤x,y≤100)(-100\le x,y\le 100)

출력

네 개의 점으로부터 같은 거리에 있는 원의 중심 좌표 (cx,cy)(cx,cy)와 반지름의 길이 rr을 공백으로 구분하여 출력한다. 출력한 원은 −100,000≤cx,cy≤100,000-100\\, 000\le cx,cy\le 100\\, 000, 0≤r≤100,0000\le r\le 100\\, 000을 만족하고 주어지는 네 점 중 어떤 두 점을 골라도 원까지의 거리의 차이가 10−310^{-3} 이하이면 정답으로 인정된다. 조건을 만족하는 원이 둘 이상인 경우 그중 아무거나 출력한다.

힌트

입력 예제는 본문에 주어진 그림과 같다. 또한 조건을 만족하는 원을 항상 찾을 수 있음이 보장된다.

예제1

  1. 예제 1

    입력
    0 0
    1 0
    2 0
    1 1
    
    예상 출력
    0.5 0.5 1.144123