#P2521. [HAOI2011] 防线修建
[HAOI2011] 防线修建
题目描述
近来A国和B国的矛盾激化,为了预防不测,A 国准备修建一条长长的防线,当然修建防线的话,肯定要把需要保护的城市修在防线内部了。
可是A国上层现在还犹豫不决,到底该把哪些城市作为保护对象呢?又由于 A 国的经费有限,所以希望你能帮忙完成如下的一个任务:
1、给出你所有的 A 国城市坐标
2、A国上层经过讨论,考虑到经济问题,决定取消对 城市的保护,也就是说 城市不需要在防线内了
3、A国上层询问对于剩下要保护的城市,修建防线的总经费最少是多少
你需要对每次询问作出回答。注意单位长度的防线花费为 。
A 国的地形是这样的,形如下图, 轴是一条河流,相当于一条天然防线,不需要你再修建。
A 国总是有两个城市在河边,一个点是 ,一个点是 ,其余所有点的横坐标均在 范围内,纵坐标均大于0。
A国有一个不在 和 的首都。 和首都这三个城市是一定需要保护的。
上图中,A,B,C,D,E 点为 A 国城市,且目前都要保护,那么修建的防线就会是 A-B-C-D,花费也就是线段 AB 的长度+线段 BC 的长度+线段 CD 的长度,如果,这个时候撤销 B 点的保护,那么防线变成下图
输入格式
第一行三个整数 分别表示河边城市和首都是 。
第二行一个整数 。
接下来 行,每行两个整数 表示 A 国的一个非首都非河边城市的坐标为 。
再接下来一个整数 ,表示修改和询问总数。
接下来 行每行要么形如 1 u
,要么形如 2
,分别表示撤销第 个城市的保护和询问。
输出格式
对于每个询问输出一行一个实数 ,表示修建防线的花费,保留两位小数。
4 2 1
2
1 2
3 2
5
2
1 1
2
1 2
2
6.47
5.84
4.47
提示
【数据范围】
对于 的数据,;
对于 的数据,,,。
所有点的坐标范围均在 以内, 数据保证没有重点。
:新增加一组 Hack 数据。