데이터 분석

면접 대비

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

요약

점 N개를 x좌표 순으로 정렬한 뒤 K개의 연속된 구간으로 나눕니다. 각 구간의 y값을 하나의 수평선으로 맞출 때 절댓값 오차 합의 최솟값을 구합니다.

문제

데이터 과학자 앨리스는 데이터를 분석하는 일을 맡았다. 각 데이터는 2차원 좌표 $(x, y)$ 로 구성된다.

데이터 분석은 2차원 평면에서 $x$ 축에 평행한 선분 $K$ 개를 찾는 과정이다. 구체적으로 다음 값들을 결정해야 한다.

각 선분의 끝을 나타내는 $x$ 좌표 $0=p_0 < p_1 < \cdots < p_K = 50\ 000$ . $i$ 번째 선분의 양 끝은 $p_{i-1}$ 과 $p_i$ 이다. 단, $1 \leq i \leq K$
각 선분의 $y$ 좌표 $m_1, m_2, \cdots, m_K$

$m_1, m_2, \cdots, m_K$ 의 값을 아무렇게나 정하면 안 된다. 분석의 정확도를 높이기 위해 오차를 정의하고, 오차가 최소가 되도록 값을 정해 줄 것이다. 오차는 다음과 같이 정의한다.

앨리스는 오차가 최소가 되도록 $p_0, \cdots, p_K$ 와 $m_1, \cdots, m_K$ 를 정하고자 한다. 각 값을 적절히 정했을 때, 데이터 분석 오차의 최솟값을 구하시오.

첫 번째 줄에 데이터의 개수 $N$ 과 찾아야 하는 선분의 개수 $K$ 가 공백으로 구분되어 주어진다.

이후 $N$ 개의 줄에 각 데이터 $(x, y)$ 가 공백으로 구분되어 주어진다. 모든 데이터의 $x$ 값은 서로 다르다.

$p_0, \cdots, p_K$ 와 $m_1, \cdots, m_K$ 의 값을 적절히 정했을 때, 데이터 분석의 오차를 출력한다. 절대 오차와 상대 오차는 $10^{-4}$ 까지 허용한다.