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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Poj2451】【半平面交模板题】【Uyuw's Concert】  

2014-04-22 19:35:39|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:求半平面交的面积。
   0.0从来没写过正经的半平面交...【不正经的也没写过很多好吧...】
   就直接是 O(nlogn)的半平面交了额...【也只有O(nlogn)的半平面交好吧...】
   写半平面交的几点注意的地方:0.0注意去掉某向量指的是两向量平行且同向,如果反向的不需要考虑【这里咱只用叉积的话就会把反向的也删除掉】,关于反向要特判出来。【0.0不过一般情况不会碰到这么特殊的吧】
   另外关于这个向量的极角排序...一直很傻很天真的以为直接排就可以了,然后今天才认识到要分象限额...
   首先判断出象限,然后对于象限不同的直接判断,对于象限相同的再叉积。【对于刚好在坐标轴的呢?咱们每一个半坐标强行规定属于一个象限即可】
    然后,对于一个浮点数,初始值最好赋作0.0,而不是0,不然可能会发生一些非常奇怪的错误【比如write(a:0:1)】

==============================

program poj2451;
const maxn=40010;
      eps=1e-5;
type point=record
     x,y:double;
     end;
     poly=record
     x,y,w:point;
     end;

var p,ans:array[0..maxn]of poly;
    q:array[0..maxn]of point;
    sav:array[0..3]of point;
    area:double;
    n:longint;

function wh(w:point):longint;
begin
  if abs(w.x)<eps then
   if w.y>0 then exit(1)
            else exit(3);
  if abs(w.y)<eps then
   if w.x>0 then exit(4)
            else exit(2);
  if (w.x>0)and(w.y>0) then exit(1);
  if (w.x<0)and(w.y>0) then exit(2);
  if (w.x<0) then exit(3)
             else exit(4);
end;

function det(a,b,c,d:point):double;
begin
  exit((b.x-a.x)*(d.y-c.y)-(b.y-a.y)*(d.x-c.x));
end;

function det(a,b,c,d:double):double;
begin
  exit(a*d-b*c);
end;

function cmp(p,q:point):boolean;
var u,v:longint;
begin
  u:=wh(p);
  v:=wh(q);
  if u<>v then
   if u<v then exit(true)
          else exit(false);
  if det(p.x,p.y,q.x,q.y)-eps>0 then exit(true);
  exit(false);
end;

function get(x,y:poly):point;
var d1,dx,t1:double;
    p:point;
begin
  d1:=det(x.w.x,-y.w.x,x.w.y,-y.w.y);
  dx:=det(y.x.x-x.x.x,-y.w.x,y.x.y-x.x.y,-y.w.y);
  t1:=dx/d1;
  p.x:=x.x.x+t1*x.w.x;
  p.y:=x.x.y+t1*x.w.y;
  exit(p);
end;

procedure qsort(l,r:longint);
var i,j:longint;
    x,y:poly;
begin
  i:=l;j:=r;
  x:=p[(l+r)shr 1];
  repeat
    while cmp(p[i].w,x.w) do inc(i);
    while cmp(x.w,p[j].w) 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;

procedure init;
var i,l,r:longint;
    zero:point;
begin
  read(n);
  for i:=1 to n do
   begin
    read(p[i].x.x,p[i].x.y,p[i].y.x,p[i].y.y);
    p[i].w.x:=p[i].y.x-p[i].x.x;
    p[i].w.y:=p[i].y.y-p[i].x.y;
   end;
  sav[0].x:=0;sav[0].y:=0;
  sav[1].x:=10000;sav[1].y:=0;
  sav[2].x:=10000;sav[2].y:=10000;
  sav[3].x:=0;sav[3].y:=10000;
  for i:=0 to 3 do
   begin
    p[n+i+1].x:=sav[i];
    p[n+i+1].y:=sav[(i+1)mod 4];
    p[n+i+1].w.x:=p[n+i+1].y.x-p[n+i+1].x.x;
    p[n+i+1].w.y:=p[n+i+1].y.y-p[n+i+1].x.y;
   end;
  inc(n,4);
  qsort(1,n);
  l:=0;r:=0;
  ans[l]:=p[1];
  for i:=2 to n do
   begin
     while (l<r)and(det(p[i].x,p[i].y,p[i].x,q[r-1])+eps<0) do dec(r);
     while (l<r)and(det(p[i].x,p[i].y,p[i].x,q[l])+eps<0) do inc(l);
     inc(r);
     ans[r]:=p[i];
     if (abs(det(ans[r].x,ans[r].y,ans[r-1].x,ans[r-1].y))<eps) then
      begin
        dec(r);
        if det(ans[r].x,ans[r].y,ans[r].x,p[i].x)-eps>0 then
          ans[r]:=p[i];
      end;
     if (l<r)then q[r-1]:=get(ans[r-1],ans[r]);
   end;
  while (l<r)and(det(ans[l].x,ans[l].y,ans[l].x,q[r-1])+eps<0) do dec(r);
  q[r]:=get(ans[l],ans[r]);
  if (r-l<=1) then
   begin
     write('0.0');
     exit;
   end;
  area:=0.0;
  zero.x:=0;zero.y:=0;
  for i:=l to r-1 do
   area:=area+det(zero,q[i],zero,q[i+1]);
  area:=area+det(zero,q[r],zero,q[l]);
  if area<0 then area:=-area;
  area:=area/2;
  if abs(area)<eps then write('0.0')
  else write(area:0:1);
end;

begin
  init;
end.



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

历史上的今天

评论

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

页脚

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