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

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

원 근사

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

요약
n개 점에 대해 제곱 잔차 합을 최소로 하는 원을 구해, 정규방정식 3x3 연립일차방정식을 푼다.
난이도

보통10점 중 6점

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

문제

직교 좌표계 위의 nn개 점 (x1x_1, y1y_1), ..., (xnx_n, yny_n)을 생각하자. 여러분은 원 x2+y2+ax+by+c=0x^2 + y^2 + ax + by + c = 0에 대한 회귀를 수행하는 프로그램을 작성해야 한다. 다시 말해, 오차를 최소로 하는 원을 찾아야 한다. 여기서 오차는 각 점과 원 사이 거리의 제곱의 합으로 측정되며, 이는 다음과 같다.

∑i=1n(xi2+yi2+axi+byi+c)2\sum_{i=1}^{n}{(x_i^2 + y_i^2 + ax_i + by_i + c)^2}

입력

입력의 첫째 줄에는 정수 nn (3 ≤ nn ≤ 40,000)이 주어진다. 그다음 nn개 줄이 이어진다. ii번째 줄에는 두 정수 xix_i와 yiy_i (0 ≤ xix_i, yiy_i ≤ 1,000)가 주어지며, 이는 ii번째 점의 좌표를 나타낸다.

모든 점이 한 직선 위에 놓이는 경우는 주어지지 않는다.

출력

회귀된 함수를 나타내는 세 정수 aa, bb, cc를 공백으로 구분해 출력한다. 출력값은 소수점 아래 세 자리까지 출력해야 하며, 오차가 0.001을 넘어서는 안 된다.

예제2

  1. 예제 1

    입력
    4
    0 0
    100 0
    100 100
    0 100
    
    예상 출력
    -100.000 -100.000 0.000
    
  2. 예제 2

    입력
    3
    0 0
    10 0
    5 100
    
    예상 출력
    -10.000 -99.750 0.000