P2521 [HAOI2011]防线修建

    • 291通过
    • 600提交
  • 题目提供者 massimodong
  • 评测方式 云端评测
  • 标签 凸包 平衡树 各省省选 2011 河南 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    近来A国和B国的矛盾激化,为了预防不测,A国准备修建一条长长的防线,当然修建防线的话,肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决,到底该把哪些城市作为保护对象呢?又由于A国的经费有限,所以希望你能帮忙完成如下的一个任务:

    1. 给出你所有的A国城市坐标

    2. A国上层经过讨论,考虑到经济问题,决定取消对i城市的保护,也就是说i城市不需要在防线内了

    3. A国上层询问对于剩下要保护的城市,修建防线的总经费最少是多少

    你需要对每次询问作出回答。注意单位1长度的防线花费为1。

    A国的地形是这样的,形如下图,x轴是一条河流,相当于一条天然防线,不需要你再修建

    A国总是有两个城市在河边,一个点是(0,0),一个点是(n,0),其余所有点的横坐标均大于0小于n,纵坐标均大于0。A国有一个不在(0,0)和(n,0)的首都。(0,0),(n,0)和首都这三个城市是一定需要保护的。

    输入输出格式

    输入格式:

    第一行,三个整数n,x,y分别表示河边城市和首都是(0,0),(n,0),(x,y)。

    第二行,一个整数m。

    接下来m行,每行两个整数a,b表示A国的一个非首都非河边城市的坐标为(a,b)。

    再接下来一个整数q,表示修改和询问总数。

    接下来q行每行要么形如1 i,要么形如2,分别表示撤销第i个城市的保护和询问。

    输出格式:

    对于每个询问输出1行,一个实数v,表示修建防线的花费,保留两位小数

    输入输出样例

    输入样例#1: 复制
    4 2 1                                
    2                                 
    1 2                               
    3 2                               
    5                                 
    2
    1 1
    2
    1 2
    2
    输出样例#1: 复制
    6.47
    5.84
    4.47

    说明

    数据范围:

    30%的数据m<=1000,q<=1000

    100%的数据m<=100000,q<=200000,n>1

    所有点的坐标范围均在10000以内, 数据保证没有重点

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