P2497 [SDOI2012]基站建设

    • 1通过
    • 63提交
  • 题目提供者 kkksc03 吉祥物
  • 评测方式 云端评测
  • 标签 各省省选 2012 山东
  • 难度 尚无评定
  • 时空限制 3000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

    一个点i如果能从另一个点j接收到信号(当且仅当x[j] < x[i]),必须满足i的接收范围与j的发射范围相切,并且需要付sqrt(r2[i])的额外费用。同时启动每一个点i都需要费用v[i].

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

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

    输入输出格式

    输入格式:

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

    记下来n行,每行三个整数x[i],r1[i],v[i],表示每个基站的坐标,发射范围以及费用。

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

    R为1..n的排列。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    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
    输出样例#1: 复制
    3501.000

    说明

    数据范围:

    对于20%的数据n<=2000

    对于60%的数据n<=100000

    对于100%的数据 n<=5*1000000,x[i],m <= 10^12,v[i] <= 10000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。