BZOJ2300 Defence - Hoblovski's Blog - 想拿Ag的蒟蒻.已经Ag滚出.
BZOJ3631 Squirrel
BZOJ3672 Ticket

BZOJ2300 Defence

Hoblovski posted @ 2014年9月14日 17:38 in Solutions with tags BZOJ 动态凸包 Treap 重载运算符 , 747 阅读
题意    给定第一象限以及正半轴上面N个点,动态删点和询问凸包周长.
        保证任何时候总有O,R(n,0)其中n是最大的横坐标以及另一个一象限内的点.
 
Tag Treap,动态凸包
 
省选之后做的题了,至于现在发只是为了试验Pascal重载运算符以及准备把购票的点分治写了.
 
离线倒着做之后变成加点动态凸包
凸包可以看做一个有序集,它的序可以使极角序不过最好用XY坐标序,学名忘了...
每次加点,判定在凸包外,之后找到这个点在凸包上的前驱后继,从前驱往前删后继往后删.
一直删到O或R,或者根据叉积判断已经不能再删了.
 
重载运算符写好了很好用...写高精度等大数据类型运算符的一定要传参但是其他时候大概可以传值.
完胜
736073        hoblovski_1      2300        Accepted        2508 kb        868 ms         Pascal        3948 B        2014-09-14 16:28:15
667985        Hoblovski        2300        Accepted        3680 kb        1340 ms        Pascal        5183 B        2014-06-09 22:02:29
 
{$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.

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter