P2521 [HAOI2011] Building the Defense Line

Recently, tensions between Country A and Country B have escalated. To guard against the unexpected, Country A plans to build a long defense line. Of course, if a defense line is built, the cities that need protection must lie inside the line. However, the leadership of Country A is still hesitant about which cities should be protected. Because the budget is limited, they want you to help with the following task: 1. You are given the coordinates of all cities in Country A. 2. After discussion, considering economic issues, the leadership decides to cancel protection for city $u$, meaning city $u$ no longer needs to be inside the defense line. 3. The leadership asks: for the remaining cities that still need protection, what is the minimal total cost to build the defense line? You need to answer each query. Note that the cost per unit length of the defense line is $1$. The terrain of Country A is as follows. As shown in the figure, the $x$-axis is a river, which serves as a natural defense line and does not need to be built.  Country A always has two cities on the riverbank: one at $(0, 0)$ and one at $(n, 0)$. The $x$-coordinates of all other points lie in $(0, n)$, and the $y$-coordinates are greater than $0$. Country A has a capital that is not at $(0, 0)$ or $(n, 0)$. The three cities $(0, 0)$, $(n, 0)$, and the capital must always be protected. In the figure above, points A, B, C, D, E are cities of Country A, and all currently need protection. Then the defense line will be A-B-C-D, and the cost is the length of segment AB plus the length of segment BC plus the length of segment CD. If, at this moment, the protection of point B is canceled, then the defense line becomes the one shown below. 

The first line contains three integers $n, x, y$, indicating that the riverbank cities and the capital are $(0, 0)$, $(n, 0)$, and $(x, y)$. The second line contains an integer $m$. The next $m$ lines each contain two integers $a, b$, indicating that the coordinates of a non-capital, non-river city are $(a, b)$. Then an integer $q$ follows, representing the total number of updates and queries. Each of the next $q$ lines is either of the form `1 u` or `2`, representing canceling the protection of the $u$-th city and an inquiry, respectively.

For each inquiry, output a real number $v$ on one line, representing the cost to build the defense line, with two decimal places.

Constraints For $30\%$ of the testdata, $1 \le m, q \le 1000$. For $100\%$ of the testdata, $1 \le m \le 10^5$, $1 \le q \le 2 \times 10^5$, $1 < n \le 10^4$. All coordinates are within $10^4$. The testdata guarantees there are no coincident points. --- ~~$\text{upd 2022.7.21}$: A new hack testdata was added.~~ This testdata was invalid and has been removed. Translated by ChatGPT 5