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 重载运算符 , 1402 阅读
题意    给定第一象限以及正半轴上面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.

 

Avatar_small
JSC Result 2021 Madr 说:
2021年12月20日 16:43

Check Jharkhand Academic Council Madrasa Board Exam Result | JAC Madarsa Result Date 2021 | JACMB Madarsa Exam Result Name | Jharkhand Academic Council Madrasa Board (JACMB) is going to release Wastania, Moulvi, Fazil, and JSC Result 2021 Madrasha BoardAlim written Exam Result on July Month the official web site. Result of Jharkhand Academic Council is very important for all presented students. According to Govt rules only Passed to take admission next class. All students can check JAC Madarsa Result 2021 by Roll Number WIse or Date of Birth Wise online. Here we are provide direct link on this page after declaration.

Avatar_small
Bushra 说:
2022年12月28日 20:40

very interesting keep posting. junk car removal bc

Avatar_small
SAAD 说:
2023年1月06日 22:55

Interesting topic for a blog. I have been searching the Internet for fun and came upon your website. Fabulous post. Thanks a ton for sharing your knowledge! It is great to see that some people still put in an effort into managing their websites. I'll be sure to check back again real soon. movers kamloops

Avatar_small
boardpaper.in 说:
2023年5月20日 23:06

The board is now ready to release the West Bengal Board 8th Class Half-Yearly And Annual Examination Model Question Paper. Student WBBSE can get WBBSE 8th Model Question Paper West Bengal Board information given here.If you still have any question then you can write it to us through comment. team is ready for your full assistance.boardpaper.in is a initiative of professional writers who have come together for dedicated news coverage of latest happenings around the country (India). Our team comprises of professional writers & citizen journalists with diverse range of interest in Journalism who are passionate

Avatar_small
otaquani 说:
2023年9月27日 20:03

Outstanding Service! Great Execution of their plans in work! They are just perfect! I would like to recommend them to everyone out there! You will not regret it! Gta 5 mod menu


登录 *


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