BZPRO
#2666. [cqoi2012]组装
内存限制：128 MiB
时间限制：3 Sec
提交
提交记录
讨论
题目描述
数轴上有
m
个生产车间可以生产零件。一共有
n
种零件，编号为1~
n
。第
i
个车间的坐标为
x
i
，生产第
p
i
种零件（1<=
p
i
<=
n
）。你需要在数轴上的某个位置修建一个组装车间，把这些零件组装起来。为了节约运输成本，你需要最小化cost(1)+cost(2)+…+cost(
n
)，其中cost(
x
)表示生产第
x
种零件的车间中，到组装车间距离的平方的最小值。
输入格式
输入第一行为两个整数
n
,
m
，即零件的种类数和生产车间的个数。以下
m
行每行两个整数
x
i
和
p
i
（1<=
p
i
<=
n
）。输入按照生产车间从左到右的顺序排列（即
x
i
<=
x
i
+1
。注意车间位置可以重复）。输入保证每种零件都有车间生产。
输出格式
输出仅一行，即组装车间的最优位置（可以和某个生产车间重合），四舍五入保留四位小数。输入保证最优位置惟一。
样例
样例输入
3 5
-1 3
0 1
2 3
4 2
5 2
样例输出
2.0000
数据范围与提示
编号
1-4
5-10
n
<=15
<=10000
m
<=25
<=100000
x
i
<=100
<=100,000
BZPRO