注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Poj1151】【矩形面积并】【Atlantis】  

2014-04-18 20:07:08|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:求矩形面积并。
   做到hnoi2012的xxxxx的时候想起来咱还从没写过矩形面积并的...突然想起连半平面交也没有写的= =,今天复习一下吧。
   做法也挺经典的了...咱们首先对X,Y都离散化一下,然后把每一条横的边去掉,只留下竖线,然后左边的设一个+1,右边的设一个-1,然后每一次维护两条扫描线,一条左端点,一条右端点,两个之间不存在其他竖线,每次处理右扫描线的事件,然后咱们移动竖线的时候用线段树维护中间哪些线条+1,哪些-1,然后统计答案即可。
    一开始以为额要打标记恩...然后写一个Update即可...然后发现自己大错特错了....之前只要把某个节点的线段删掉没有咱就将它的覆盖长度变成0,这是极不好的....咱们每一个线段变成了0的时候用它的两个儿子来更新(如果没儿子才是0)。这样子就不需要写懒标记了(写了半天的懒标记额...)
    主要是复习线段树。
==================
const eps=1e-5;
type node=record
l,r,a,b:longint;
sum:double;
cover:longint;
end;
point=record
x,y,xx:double;cnt:longint;
end;
arr=array[0..10000]of double;

var t:array[0..10000]of node;
p:array[0..10000]of point;
y:array[0..10000]of double;
n,tot,tt:longint;

procedure maintain(x:longint);
begin
t[x].sum:=t[t[x].l].sum+t[t[x].r].sum;
end;

{procedure push(x:longint);
begin
if t[x].l=0 then exit;
if t[x].cover>0 then
begin
inc(t[t[x].l].dep,t[x].cover);
inc(t[t[x].r].dep,t[x].cover);
if t[t[x].l].dep=t[x].cover then
t[t[x].l].sum:=y[t[t[x].l].b]-y[t[t[x].l].a];
if t[t[x].r].dep=t[x].cover then
t[t[x].r].sum:=y[t[t[x].r].b]-y[t[t[x].r].a];
t[t[x].l].cover:=t[t[x].l].cover+t[x].cover;
t[t[x].r].cover:=t[t[x].r].cover+t[x].cover;
t[x].cover:=0;
end;
if t[x].cover<0 then
begin
inc(t[t[x].l].dep,t[x].cover);
inc(t[t[x].r].dep,t[x].cover);
if t[t[x].l].dep=0 then
t[t[x].l].sum:=0;
if t[t[x].r].dep=0 then
t[t[x].r].sum:=0;
t[t[x].l].cover:=t[t[x].l].cover+t[x].cover;
t[t[x].r].cover:=t[t[x].r].cover+t[x].cover;
t[x].cover:=0;
end;
end; }

procedure build(l,r:longint);
var mid,now:longint;
begin
inc(tot);now:=tot;
t[now].a:=l;t[now].b:=r;
t[now].sum:=0;t[now].cover:=0;
t[now].l:=0;t[now].r:=0;
if l+1<r then
begin
mid:=(l+r)shr 1;
t[now].l:=tot+1;build(l,mid);
t[now].r:=tot+1;build(mid,r);
end;
end;

procedure insert(l,r:longint;x,c:longint);
var mid:longint;
begin
if (y[l]-eps<=y[t[x].a])and(y[r]+eps>=y[t[x].b])then
begin
inc(t[x].cover,c);
t[x].sum:=y[t[x].b]-y[t[x].a];
if (c=-1)and(t[x].cover<=0)then
if t[x].a+1<t[x].b then maintain(x)
else t[x].sum:=0;
exit;
end;
mid:=(t[x].a+t[x].b)shr 1;
if mid>l then insert(l,r,t[x].l,c);
if mid<r then insert(l,r,t[x].r,c);
if t[x].cover=0 then maintain(x);
end;

procedure qsort(l,r:longint;var a:arr);
var i,j:longint;x,y:double;
begin
i:=l;j:=r;
x:=a[(l+r)shr 1];
repeat
while a[i]+eps<x do inc(i);
while a[j]-eps>x do dec(j);
if i<=j then
begin
y:=a[i];a[i]:=a[j];a[j]:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r,a);
if j>l then qsort(l,j,a);
end;

procedure qsort(l,r:longint);
var i,j:longint;y:point;
x:double;
begin
i:=l;j:=r;
x:=p[(l+r)shr 1].xx;
repeat
while p[i].xx+eps<x do inc(i);
while p[j].xx-eps>x do dec(j);
if i<=j then
begin
y:=p[i];p[i]:=p[j];p[j]:=y;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;

function find(x:double;tot:longint):longint;
var l,r,mid:longint;
begin
l:=1;r:=tot;
while l<r do
begin
mid:=(l+r)shr 1;
if abs(y[mid]-x)<eps then exit(mid);
if y[mid]>x then r:=mid-1
else l:=mid+1;
end;
exit(l);
end;

procedure init;
var i,sav,sav2:longint;
x1,y1,x2,y2,ans:double;
begin
tot:=0;
for i:=1 to n do
begin
read(x1,y1,x2,y2);
inc(tot);y[tot]:=y1;
p[tot].x:=y1;p[tot].y:=y2;p[tot].cnt:=1;p[tot].xx:=x1;
inc(tot);y[tot]:=y2;
p[tot].x:=y1;p[tot].y:=y2;p[tot].cnt:=-1;p[tot].xx:=x2;
end;
qsort(1,tot,y);
sav:=0;
y[0]:=-111111;
for i:=1 to tot do
if y[sav]<>y[i] then
begin
inc(sav);
y[sav]:=y[i];
end;
qsort(1,tot);
sav2:=tot;tot:=0;
build(1,sav2);
ans:=0;tot:=sav2;
i:=1;
p[tot+1].xx:=-1.52;
ans:=0;
while i<=tot do
begin
while (i<=tot)and(abs(p[i].xx-p[i+1].xx)<eps) do
begin
insert(find(p[i].x,sav),find(p[i].y,sav),1,p[i].cnt);
inc(i);
end;
insert(find(p[i].x,sav),find(p[i].y,sav),1,p[i].cnt);
if i<tot then ans:=ans+t[1].sum*(p[i+1].xx-p[i].xx);
inc(i);
end;
writeln('Total explored area: ',ans:0:2);
writeln;
end;

begin
read(n);
tt:=0;
while n<>0 do
begin
inc(tt);
writeln('Test case #',tt);
init;
read(n);
end;
end.





  评论这张
 
阅读(17)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017