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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1074】【SCOI2007】【折纸】  

2014-03-28 16:37:04|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    bzoj1073 求无环k短路不会做...咱先跳过....
    然后本来想这道题也跳的(咱是蒟蒻嘛= =),然后去问了下CB君,CB神犇说这也很简单嘛,就是一道模拟嘛233.= =.
    其实一看到题目就当场吓傻了......= =
    题目大意:给乃一张 100*100的纸片,然后按次序给出n(n<=8)个向量,每次把这个向量右边的部分的纸折向左边(就像生活中的折纸),然后最后折成一个东西。然后询问这个东西上m个点(m<=50)所包含的纸的层数是多少....
    一开始以为是半平面交有关的东西,然后 发现就算在同一个半平面交最后的层数也可能不同。所以就不会做了= =。
    然后就是CB君的思想:
    其实咱们可以发现一点,就是实际上层数就是有多少点经过上面的那一些变换,然后变换到这个点了,咱们可以暴力枚举某个点是经过哪几个变换然后到达这个点的,然后咱们倒着做,求出原来的那个点,并判断这个的合法性,如果合法,这个的答案ans++。复杂度为O(2^n*m)。那么问题在于两个,如果判断合法以及如何求出原来的点。
    判断合法性嘛....就直接顺着模拟一遍就可以了...
    求出原来的点就是倒着对称即可,关于对称点的计算,假设咱们知道一个点(x0,y0)和一条直线 (x1,y1)-(x2,y2),那么对称点如何算??一点高中数学嘛....
    咱们先求直线上垂直的那个点,然后一个向量即可。
    首先垂直有 (x-x0)(x1-x2)+(y-y0)(y1-y2)=0
    然后在直线上有 (x2-x1)(y-y1)-(x-x1)*(y2-y1)=0
    解这两个方程就可以了。
    然后对称点就是 (x+x-x0,y+y-y0)
    然后还有就是如果刚好在某一层的边界的话就不需要统计,由于某一层的边界实际上就是原来那张纸的边界上的点或者对称轴上的点,也就是说,如果某个点变换之后在边界处或者对称轴处就直接cut掉。
    然后注意判相等要加精度....这里被坑一次。
    然后没了....
===========================

program bzoj1074;
const eps=1e-6;
type point=record
     x,y:double;
     end;
     line=record
     x,y:point;
     end;

var l:array[0..10]of line;
    c:array[0..300]of point;
    n,ans,m:longint;
    p:point;

function det(x,y,z,w:point):double;
begin
  exit((y.x-x.x)*(w.y-z.y)-(y.y-x.y)*(w.x-z.x));
end;

function det(x,y,z,w:double):double;
begin
  exit(x*w-y*z);
end;

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

function cal(p:point;l:line):point;
var q:point;
    d,dx,dy,a,b:double;
begin
  a:=p.x*(l.x.x-l.y.x)+p.y*(l.x.y-l.y.y);
  b:=l.x.x*(l.x.y-l.y.y)-l.x.y*(l.x.x-l.y.x);
  d:=det(l.x.x-l.y.x,l.x.y-l.y.y,l.x.y-l.y.y,l.y.x-l.x.x);
  dx:=det(a,l.x.y-l.y.y,b,l.y.x-l.x.x);
  dy:=det(l.x.x-l.y.x,a,l.x.y-l.y.y,b);
  q.x:=dx/d;
  q.y:=dy/d;
  q.x:=q.x+q.x-p.x;
  q.y:=q.y+q.y-p.y;
  exit(q);
end;

procedure main;
var i,j,k,w:longint;
    qq:double;
    q:point;
    can:boolean;
begin
  ans:=0;k:=0;
  for i:=0 to 1<<n-1 do
   begin
     j:=i;q:=p;w:=n;
     while j<>0 do
      begin
        if j and 1=1 then
         if det(l[w].y,l[w].x,l[w].y,q)<eps then
          q:=cal(q,l[w]);
        dec(w);
        j:=j shr 1;
      end;
     inc(k);c[k]:=q;
   end;
  qsort(1,k);
  for i:=1 to k do
   begin
     if (c[i].x<=eps)or(c[i].x+eps>=100)or(c[i].y<=eps)or(c[i].y+eps>=100)then continue;
     if (i<>1)and(c[i].x=c[i-1].x)and(c[i].y=c[i-1].y)then continue;
     q:=c[i];
     can:=true;
     for j:=1 to n do
      begin
      qq:=det(l[j].x,l[j].y,l[j].x,q);
      if abs(qq)<eps then begin can:=false;break;end;
      if qq<-eps then
        q:=cal(q,l[j]);
      end;
     if (abs(q.x-p.x)<eps)and(abs(q.y-p.y)<eps)and(can)then inc(ans);
   end;
  writeln(ans);
end;

procedure init;
var i:longint;
begin
  read(n);
  for i:=1 to n do
    read(l[i].x.x,l[i].x.y,l[i].y.x,l[i].y.y);
  read(m);
  for i:=1 to m do
   begin
     read(p.x,p.y);
     main;
   end;
end;

begin
  init;
end.

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

历史上的今天

评论

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

页脚

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