P3162 [CQOI2012] Assembly

There are $m$ production workshops on the number line that can produce parts. There are $n$ types of parts, numbered $1 \sim n$. The $i$-th workshop is located at coordinate $x_i$ and produces part type $p_i$ ($1 \le p_i \le n$). You need to build an assembly workshop at some position on the number line to assemble these parts. To minimize transportation cost, you need to minimize $\,$ $cost_1 + cost_2 + \ldots + cost_n$, where $cost_x$ denotes the minimum squared distance from the assembly workshop to any workshop that produces part type $x$.

The first line contains two integers $n$, $m$, the number of part types and the number of production workshops. Each of the following $m$ lines contains two integers $x_i$ and $p_i$ ($1 \le p_i \le n$). The input is ordered from left to right by workshop position (i.e., $x_i \le x_{i+1}$; note that positions may repeat). It is guaranteed that every part type has at least one workshop producing it.

Output a single line: the optimal location of the assembly workshop (it may coincide with a production workshop), rounded to four decimal places. It is guaranteed that the optimal location is unique.

- Test points 1–4: $n \le 15$, $m \le 25$, $x_i \le 100$. - Test points 5–10: $n \le 10^4$, $m \le 10^5$, $x_i \le 10^5$. Translated by ChatGPT 5