BZOJ2300 Defence

{$INLINE ON}
program bzoj2300;
 
type point=record x,y:longint; end;
     pnode=^tnode;
     tnode=record
        v:point;
        p:longint;
        l,r:pnode;
     end;
 
const maxn=100017;
      maxm=100017;
      maxint=longint($3f3f3f3f);
 
var p:array[0..maxn] of point;
    flag:array[0..maxn] of boolean;
    op:array[0..maxm] of longint;
    ans:array[0..maxm] of extended;
    lmost,rmost:point;
    n,m,maxx:longint;
    root,null:pnode;
    curans:extended;
 
operator <(a,b:point) c:boolean; inline; begin exit((a.x<b.x)or((a.x=b.x)and(a.y<b.y))); end;
operator =(a,b:point) c:boolean; inline; begin exit((a.x=b.x)and(a.y=b.y)); end;
operator *(a,b:point) c:int64; inline; begin c:=int64(a.x)*b.y-int64(b.x)*a.y; end; 
operator -(a,b:point) c:point; inline; begin c.x:=b.x-a.x; c.y:=b.y-a.y; end;
function dist(a,b:point):extended; inline; begin exit(sqrt(sqr(a.x-b.x)+sqr(a.y-b.y))); end;
 
procedure treap_init;                                                                           begin
new(null); with null^ do begin v.x:=-1; v.y:=-1; p:=maxint; l:=null; r:=null; end; root:=null;  end;
 
procedure lrot(var i:pnode); var j:pnode;
begin j:=i^.r; i^.r:=j^.l; j^.l:=i; i:=j; end;
 
procedure rrot(var i:pnode); var j:pnode;
begin j:=i^.l; i^.l:=j^.r; j^.r:=i; i:=j; end;
 
procedure insert(var i:pnode;j:point);
begin
if i=null then begin
        new(i); with i^ do begin
                v:=j; p:=random(maxint); l:=null; r:=null; 
        end;
end else if j<i^.v then begin
        insert(i^.l,j); if i^.l^.p<i^.p then rrot(i); 
end else begin
        insert(i^.r,j); if i^.r^.p<i^.p then lrot(i); 
end;
end;
 
procedure delete(var i:pnode;j:point);
begin
if j=i^.v then
        if i^.l=null then i:=i^.r 
        else if i^.r=null then i:=i^.l
        else if i^.l^.p<i^.r^.p then begin
                rrot(i); delete(i^.r,j);
        end else begin
                lrot(i); delete(i^.l,j);
        end
else if j<i^.v then delete(i^.l,j) else delete(i^.r,j);
end;
 
function prev(i:pnode;j:point):point; inline;
begin
prev:=lmost; while i<>null do
        if not(i^.v<j) then i:=i^.l
        else begin prev:=i^.v; i:=i^.r; end;
end;
 
function next(i:pnode;j:point):point; inline;
begin
next:=rmost; while i<>null do
        if (i^.v<j)or(i^.v=j) then i:=i^.r
        else begin next:=i^.v; i:=i^.l; end;
end;
 
procedure addpoint(a:point);
var rp,lp,np:point;
begin
lp:=prev(root,a); rp:=next(root,a); if (a-lp)*(rp-lp)>=0 then exit;
curans:=curans-dist(lp,rp);
while not(lp=lmost) do begin
        np:=prev(root,lp); if (a-lp)*(np-lp)>=0 then begin
                curans:=curans-dist(lp,np); delete(root,lp); lp:=np;
        end else break;
end; curans:=curans+dist(lp,a);
while not(rp=rmost) do begin
        np:=next(root,rp); if (a-rp)*(np-rp)<=0 then begin
                curans:=curans-dist(rp,np); delete(root,rp); rp:=np;
        end else break;
end; curans:=curans+dist(rp,a); insert(root,a);
end;
 
procedure work;
var i,j:longint;
begin
readln(maxx,p[0].x,p[0].y); fillchar(flag,sizeof(flag),true);
readln(n); for i:=1 to n do readln(p[i].x,p[i].y); 
readln(m); for i:=1 to m do begin read(j);
        case j of
                1:begin readln(op[i]); flag[op[i]]:=false; end;
                2:op[i]:=-1;
        end;
end; curans:=2*maxx;
lmost.x:=0; lmost.y:=0; rmost.x:=maxx; rmost.y:=0; 
insert(root,lmost); insert(root,rmost); for i:=0 to n do
        if flag[i] then addpoint(p[i]);
for i:=m downto 1 do if op[i]=-1 then ans[i]:=curans else addpoint(p[op[i]]);
for i:=1 to m do if op[i]=-1 then writeln((ans[i]-maxx):0:2);
end;
 
begin
treap_init;
work;
end.