시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 512 MB | 9 | 3 | 3 | 33.333% |
You are given $n$ lines on the plane, defined by equations of the form $y = a_i x + b_i$. You can change the coefficients of a line from $(a, b)$ to $(a', b')$ at the cost of $|a - a'| + |b - b'|$ rubles. You can do this operation an arbitrary number of times with arbitrary lines, and the resulting coefficients can be any real numbers. Your goal is to make all the lines share a common point.
Let $C$ be the set of total costs of operations leading to the goal. Find $\inf C$, that is, the tight lower bound for the total cost.
The first line contains a positive integer $n$ ($1 \le n \le 10^5$), the number of lines.
Each of the next $n$ lines contains two integers $a_i$ and $b_i$ ($|a_i|, |b_i| \le 10^6$).
Print the answer on a single line with absolute or relative error no more than $10^{-6}$.
3 0 0 1 -1 -1 0
0.500000000000000
5 4 1 3 0 3 1 2 0 1 2
3.000000000000000
In the first example, it is enough to change $b$ of the first line to $-0.5$.