Logo CSP.ac

CSP.ac

1 s / 256 MB

#122. 【冬令营】Day2T12-基站选择

统计

【问题描述】

平面直角坐标系中有n个信号点。现在要建立一个基站,覆盖所有的信号点。

一个基站的覆盖范围是一个正整数d,如果一个点与基站的曼哈顿距离不超过d,那么这个点就能被覆盖。

有m个地点可以用来建立基站,第i个地点有一个费用系数vi。如果你在第i个地点建立一个覆盖范围为di的基站,那么费用是vi与di的乘积。

现在,你需要从这m个地点中选择一个地点用来建立基站,基站的覆盖范围由你决定,要求能覆盖所有信号点。

你需要找出费用最小的建立方案。

【输入格式】

第一行两个正整数n、m

接下来n行,每行两个正整数xi,yi。表示第i个信号点的坐标是(xi,yi)

接下来m行,每行三个正整数xj,yj,vj。表示第j个可以用来建立基站的地点的坐标是(xj,yj),费用系数是vj。

【输出格式】

输出一行一个数,建立基站的最小费用。

注意基站的覆盖范围虽然可以由你决定,但必须是正整数。

【样例输入】

3 2
1 5
2 3
6 1
3 3 7
3 2 9

【样例输出】

35

【样例解释】

选择(3,3),建立覆盖范围为5的基站,所有信号点到(3,3)的曼哈顿距离都不超过5,都能被覆盖。费用是5*7=35

【数据规模和约定】

对于30%的数据, n,m<=10

对于60%的数据, n,m<=1000

对于100%的数据, n,m<=100000,1<=xi,yi,xj,yj,vj<=10^9