#2300. [HAOI2011] 防线修建

[HAOI2011] 防线修建

题目描述

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

  1. 给出你所有的 A 国城市坐标;
  2. A 国上层经过讨论,考虑到经济问题,决定取消对 uu 城市的保护,也就是说 uu 城市不需要在防线内了;
  3. A 国上层询问对于剩下要保护的城市,修建防线的总经费最少是多少你需要对每次询问作出回答。注意单位长度的防线花费为 11

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

Failed loading image.

A 国总是有两个城市在河边,一个点是 (0,0)(0,0),一个点是 (n,0)(n,0),其余所有点的横坐标均在 (0,n)(0,n) 范围内,纵坐标均大于 00。A 国有一个不在 (0,0)(0,0)(n,0)(n,0) 的首都。(0,0),(n,0)(0,0),(n,0) 和首都这三个城市是一定需要保护的。上图中,AABBCCDDEE 点为 A 国城市,且目前都要保护,那么修建的防线就会是 ABCDA-B-C-D,花费也就是线段 ABAB 的长度 ++ 线段 BCBC 的长度 ++ 线段 CDCD 的长度,如果,这个时候撤销 B 点的保护,那么防线变成下图:

Failed loding image.

输入格式

第一行三个整数 n,x,yn,x,y 分别表示河边城市和首都是 (0,0),(n,0),(x,y)(0,0),(n,0),(x,y)。第二行一个整数 mm。接下来 mm 行,每行两个整数 a,ba,b 表示 A 国的一个非首都非河边城市的坐标为 (a,b)(a,b)。再接下来一个整数 qq,表示修改和询问总数。接下来 qq 行每行要么形如 1 u,要么形如 2,分别表示撤销第 uu 个城市的保护和询问。

输出格式

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

4 2 1
2
1 2
3 2
5
2
1 1
2
1 2
2
6.47
5.84
4.47

数据范围与约定

对于 30%30\% 的数据,1m,q1031\le m,q \le 10^3
对于 100%100\% 的数据,1m1051\le m \le 10^51q2×1051\le q \le 2 \times 10^51<n1041 < n \le 10^4。所有点的坐标范围均在 10410^4 以内,数据保证没有重点。