【bzoj2300】[HAOI2011]防线修建

2014年12月1日2,5964

Description

近来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)和首都这三个城市是一定需要保护的。

上图中,A,B,C,D,E点为A国城市,且目前都要保护,那么修建的防线就会是A-B-C-D,花费也就是线段AB的长度+线段BC的长度+线段CD的长度

如果,这个时候撤销B点的保护,那么防线变成下图

Input

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

第二行,一个整数m。

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

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

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

Output

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

Sample Input

4 2 1
2
1 2
3 2
5
2
1 1
2
1 2
2

Sample Output

6.47
5.84
4.47
数据范围:
30%的数据m<=1000,q<=1000
100%的数据m<=100000,q<=200000,n>1
所有点的坐标范围均在10000以内, 数据保证没有重点

题解

离线后问题变成维护动态凸壳,只有插入点的操作

诶用个set就可以了

插入点x,判断x是否在凸壳外,然后维护x两边的凸壳。。。

 

  • 游客25038号2015年3月27日 下午3:05 回复

    pascal选手怎么办

    #1  
    • hzwer2015年3月27日 下午4:35 回复
      admin

      TAT

      #11
    • uva.onlinejudge.org2016年6月17日 下午4:07 回复

      用treap代替

      #11
  • 伪日常系LordNanoApe2015年5月4日 下午7:44 回复

    56行的代码和72行的代码重复,觉得应该删去56行的insert。

    #2