markdown版题面

题目描述：

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

为了简化问题，我们假设移动公司，所有的基站、up主家位于同一条直线上，他们都位于这一条直线上的某一点

x

，这些点不会重合。每个基站发射和接收的范围都是一个切于地面的圆，发射的半径

r

是固定的，接收半径

r'

是可调的的。如下图：

一个点

i

如果能从另一个点

j

接收到信号（当且仅当

x_j<x_i

），必须满足

i

的接收范围与j的发射范围相切，并且需要付

\sqrt{r'_i}

的额外费用。同时启动每一个点

i

都需要费用

v_i

。

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

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

CPP

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

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

![](https://cdn.luogu.com.cn/upload/pic/1623.png)

一个点 $i$ 如果能从另一个点 $j$ 接收到信号（当且仅当 $x_j<x_i$），必须满足 $i$ 的接收范围与j的发射范围相切，并且需要付 $\sqrt{r'_i}$ 的额外费用。同时启动每一个点 $i$ 都需要费用 $v_i$。

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

![](https://cdn.luogu.com.cn/upload/pic/1624.png)

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

输入格式：

第一行两个整数

n

，

m

。表示基站个数（包括移动公司），up 主家的坐标。（保证大等于所以基站的坐标）

记下来

n

行，每行三个整数

x_i

，

r_i

，

v_i

，表示每个基站的坐标，发射范围以及费用。

x_i

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

r

为

1\dots n

的排列。

CPP

第一行两个整数 $n$，$m$。表示基站个数（包括移动公司），up 主家的坐标。（保证大等于所以基站的坐标）

记下来 $n$ 行，每行三个整数 $x_i$，$r_i$，$v_i$，表示每个基站的坐标，发射范围以及费用。

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

$r$ 为 $1\dots n$ 的排列。

输出格式：

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

CPP

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

数据范围：

对于

100\%

的数据

n\le5\times 10^5

，

x_i,m \le 10^{12}

，

v_i \le 10000

CPP

对于 $100\%$ 的数据 $n\le5\times 10^5$，$x_i,m \le 10^{12}$，$v_i \le 10000$

讨论操作

回复

相关推荐

markdown版题面