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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1069】【SCOI2007】【最大土地面积】  

2014-03-24 19:30:07|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:给乃一些点,求由这些点构成的四边形中面积最大的。
    首先求凸包,然后枚举凸包上的两个点作为该四边形的对角线,然后剩余的点就是两个凸壳,然后咱们求两个凸壳距离这两个点的最远点,可以直接二分然后再用类似旋转卡壳的方法判断是否最远即可,复杂度O(n^2logn)。
    然后就TLE了...(这才发现总时限才1s233)
    然后发现实际上枚举凸包上两个点简直是233的.....假设咱们枚举了凸包上两个点a,b,求出了其最远点c,然后咱们把b移动到一个相邻点b',咱们会发现,c也是会单调移动的!(貌似这个才叫旋转卡壳?233),所以求出所有的这种三角形只需要O(n^2)的复杂度,然后暴力枚举配三角形即可= =,咱是傻叉了。
  
=================================

program bzoj1069;
const maxn=2010;
type point=record
     x,y:double;
     end;

var p,st:array[0..maxn*2]of point;
    top,n:longint;
    area:array[0..maxn,0..maxn]of double;
    ans:double;

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 check(x,y,z,w:point):boolean;
begin
  exit(det(x,y,z,w)<=0)
end;

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

procedure init;
var i,j,tmp,k:longint;
    u,v:point;
begin
  read(n);
  for i:=1 to n do
   read(p[i].x,p[i].y);
  qsort(1,n);
  top:=0;
  for i:=1 to n do
   begin
     while(top>1)and(check(st[top-1],st[top],st[top],p[i]))do dec(top);
     inc(top);
     st[top]:=p[i];
   end;
  j:=top;
  for i:=n-1 downto 1 do
   begin
     while(top>j)and(check(st[top-1],st[top],st[top],p[i]))do dec(top);
     inc(top);
     st[top]:=p[i];
   end;
  if n>1 then dec(top);
  for i:=top+1 to top+top do
    st[i]:=st[i-top];
  ans:=0;
  for i:=1 to top do
  begin
    tmp:=i;area[i][i]:=0;
    for j:=i+1 to i+top-1 do
     begin
       while (tmp<j)and(check(st[i],st[j],st[tmp],st[tmp+1])) do inc(tmp);
       if j>top then k:=j-top else k:=j;
       area[i][k]:=abs(det(st[i],st[j],st[i],st[tmp]))/2;
     end;
  end;
  for i:=1 to top do
   for j:=i+1 to top do
    if ans<area[i][j]+area[j][i] then
     ans:=area[i][j]+area[j][i];
  write(ans:0:3);
end;

begin
  init;
end.


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

历史上的今天

评论

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

页脚

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