#P2497. [SDOI2012] 基站建设

    ID: 1445 Type: RemoteJudge 2000ms 512MiB Tried: 3 Accepted: 2 Difficulty: 6 Uploaded By: Tags>动态规划dp2012线段树各省省选山东cdq 分治斜率优化Splay

[SDOI2012] 基站建设

题目描述

up 主家终于买电脑了,但是接下来有各种问题要处理。首要解决的问题就是网络问题。他要从移动公司开始,通过一些基站来传递网络到他家。

为了简化问题,我们假设移动公司,所有的基站、up 主家位于同一条直线上,他们都位于这一条直线上的某一点 xx,这些点可能会重合。每个基站发射和接收的范围都是一个切于地面的圆,发射的半径 rr 是固定的,接收半径 rr' 是可调的的。如下图:

一个点 ii 如果能从另一个点 jj 接收到信号(当且仅当 xj<xix_j<x_i),必须满足 ii 的接收范围与 jj 的发射范围相切,并且需要付 ri\sqrt{r'_i} 的额外费用。同时启动每一个点 ii 都需要费用 viv_i

当然一个点如果能够发射的 up 主家只需要这个点的发射范围与 up 主家所在的竖线相切或相交即可,如下图:

当然费用越少就越好咯,于是 up 主想要请你帮他的忙。

输入格式

第一行两个整数 n,mn, m。表示基站个数(包括移动公司),up 主家的坐标。(保证大于等于所有基站的坐标)

记下来 nn 行,每行三个整数 xix_irir_iviv_i,表示每个基站的坐标,发射范围以及费用。

xix_i 是按照坐标从小到大输入的,移动公司位于最小的那个坐标。

rr1n1\dots n 的排列。

输出格式

一个实数,保留小数点后三位。

10 33
5 4 660
10 2 2040
11 6 3207
14 5 2006
18 3 6130
19 9 3363
22 1 1265
25 8 2836
27 10 7961
29 7 9075
3501.000

提示

对于 100%100\% 的数据 n5×105n\le5\times 10^5xi,m1012x_i,m \le 10^{12}vi10000v_i \le 10000