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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj2731】【Hnoi2012】【三角形覆盖问题】  

2014-04-21 15:45:05|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:给出一堆等腰三角形,求面积并。
    比较容易YY到矩形...话说咱矩形也没做过额...明天去做一道0.0...

    然后感觉等腰三角形的面积并貌似和矩形什么关系都没有额....这道题唯一的感觉就是可以暴力求交点,然后搞成一个个梯形,话说这样写会不会特别麻烦额...更重要的是咱根本就没写过...
    先致敬那些换了无数解法的童鞋们0.0比如这一位:wshjzaa君 【好吧戳手,竟然把wsh君的名字打错了= =】
     题解就看TA的就可以了吧,貌似时间已经不够写题解了的感觉了= =
     首先来是做法...有一种非常暴力的做法就是自底向上暴力做,每一次用一个数组标记某个点是否被占领,然后求出上面的有多少个单位格子被标记,然后用每两次的和/2加起来就是答案。实际上就是暴力剖分成梯形。这个暴力得使用双向链表来维护,即每一次扫描的时候将每一个链表内的三角形的右端点--,如果超出范围了就把它从链表删去,然后再删除完之后再插入,为了方便插入咱们把y排序即可。这样插入便是按排序的顺序。
     这样子暴力,每一个等腰三角形的腰长若为L,则需更新∑L次(插入一次,删除一次),然后需要扫描N个三角,即 O(∑LN)。
     这里咱们需要证明相邻的两个之间的图形必然是多个梯形构成的。
     这个实际上就是考虑某一y坐标的横截面,考虑y+1的横截面,显然它们的左边缘是不会变化的【假如会变化的就与等腰三角矛盾了】,然后右边缘会减少1,所以每一个都是这样的,这就是一个直角梯形的集合,然后每一个累加就会发现实际上就是 y 被三角形覆盖的线段长度+ y+1 被三角形覆盖的线段长度 除以2。 
 
============================

program bzoj2731;
type tri=record
     x,y,l,r:longint;
     end;

var e:array[0..10010]of tri;
    l,r:array[0..10010]of longint;
    w:array[0..2000010]of longint;
    n,maxx:longint;
    tot,last:int64;
    ans:double;

procedure qsort(l,r:longint);
var i,j,x:longint;
    y:tri;
begin
  i:=l;j:=r;
  x:=e[(l+r)shr 1].y;
  repeat
    while e[i].y<x do inc(i);
    while e[j].y>x do dec(j);
    if i<=j then
     begin
       y:=e[i];e[i]:=e[j];e[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;

procedure init;
var i,d,h,j,k,q:longint;
    area:double;
begin
  read(n);
  maxx:=0;q:=1;ans:=0;tot:=0;
  for i:=1 to n do
   begin
     read(e[i].x,e[i].y,d);
     e[i].l:=e[i].x;
     e[i].r:=e[i].x+d-1;
     if maxx<e[i].y+d then maxx:=e[i].y+d;
   end;
  qsort(1,n);
  fillchar(l,sizeof(l),0);
  fillchar(r,sizeof(r),0);
  fillchar(w,sizeof(w),0);
  for h:=0 to maxx+1 do
   begin
     last:=tot;
     j:=r[0];
     while j<>0 do
      begin
        i:=e[j].r;
        dec(e[j].r);
        if e[j].r<e[j].l then
         begin
           r[l[j]]:=r[j];
           l[r[j]]:=l[j];
           k:=l[j];
           l[j]:=0;r[j]:=0;
           j:=k;
         end;
        dec(w[i]);
        if w[i]=0 then dec(tot);
        j:=r[j];
      end;
     ans:=ans+last+tot;
     while (q<=n)and(e[q].y=h) do
      begin
        if e[q].l>e[q].r then
         begin
           inc(q);
           continue;
         end;
        j:=r[0];
        while j<>0 do
         begin
          if (e[j].l<=e[q].l)and(e[j].r>=e[q].r) then break;
          j:=r[j];
         end;
        if j<>0 then
         begin
           inc(q);
           continue;
         end;
        l[r[0]]:=q;r[q]:=r[0];l[q]:=0;r[0]:=q;
        for j:=e[q].l to e[q].r do
         begin
           if w[j]=0 then inc(tot);
           inc(w[j]);
         end;
        inc(q);
      end;
   end;
  area:=ans/2;
  write(area:0:1);
end;

begin
  init;
end.

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

历史上的今天

评论

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

页脚

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