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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【某迈克杯】【迈克家的果园】  

2013-10-26 22:02:07|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    虽然是爆0,但还是得写一点东西防止遗忘,这些题都很不错的。
    问题就是给定平面上的N个格点(N<=5000),求是否存在以这些格点中的四个为顶点的正方形,并求出满足条件且包含了最多格点的正方形。
    以为自己可以可以过的...感觉打击好大唔~~。首先我们得暴力枚举两点i,j,对于这两个点,我们可以构造出两个正方形,然后再检查这两个正方形的另外两个顶点是否存在。这里可以使用HASH用O(1)的时间,但是咱不敢,写了个貌似邻接表一样的索引,在数据随机的情况下还是很不错的。对于两个点的坐标设它为 X[I],X[J],Y[I],Y[J],我们为了求另一点坐标,可以构造向量 (p,q),其中
  p=x[i]-x[j],q=y[i]-y[j],那么与该向量垂直的向量就是 (-q,p)或者(q,-p),则两个正方形的两个顶点分别为 (x[j]+q,y[j]-p)(x[j]-q,y[j]+p),然后对于剩下一个点就是 (x[i]+x-x[j],y[i]+y-y[j]),当我们判断这两个点在格点中时候,就可以计算该正方形内的格点数了,这里使用到了一个以前看到过的奇葩定理(皮克定理),其内容是:
   一个平面不自交图形的顶点都为格点,则其面积等于 a+b/2-1,a为该图形内部的点,b为该图形边界的点。证明在网上有很多,主要是从三角形推广开来。所以我们要求格点,可以先求正方形的面积,它为 (x[i]-x[j])^2+(y[i]-y[j])^2,很容易算,它就等于 a+b/2-1,我们只要算出b就可以得到a,则格点数为a+b。那么关键就是求b。
   对于b,我们考察一条线段的两端分别为i,j问题就是求这条线段包含的格点,我们知道两端坐标为 x[i],x[j],y[i],y[j],我们依旧构造向量 (x[i]-x[j],y[i]-y[j]),可以证明原来在线段上的格点都还在该向量上,因为减去的x[j],y[j]是整数,所以我们就只需要求线段
(0,0)-(i,j)上的格点数就可以了。
   这些格点(x,y)满足方程 x*j=y*i,也就是说,它求的就是在i*j以内的i与j的公倍数的个数....
   然后我们知道第一个公倍数为 i*j/gcd(i,j),最后一个公倍数为 i*j,则其个数为gcd(i,j)个,即答案为gcd(i,j)+1(这里还有个(0,0)没有算进去,所以b=2*(gcd(x[i]-x[j],y[i]-y[j])+gcd(x-x[j],y-y[j]))(对称性并去掉重复)
那么a=sq+1-b/2,则此题就可以完美解决了,枚举的复杂度为o(n^2),查找的复杂度看选择的数据结构,HASH表则为O(1),但是此题数据范围有10^9,还是别开这么大为妙(貌似题目可以允许开这么大),或者对以X为第一关键字,Y为第二关键字排序再二分(这个很难写,但是可行),复杂度为O(LOGN),所以复杂度理想为 O(N^2logN)级别的,对于N=5000,可以承受。
    突然才想起来自己犯了一个很傻的错误,只判断了第三个点是否在格点里,第四个点忘记判断了!
   附未排序的错误程序(这里得写一个关键字的快排以及对第四个点进行特判,应该就可以AC了,可惜比赛截止后就不让测试了,可惜...)

program mike;
var x,y:array[1..5000]of longint;
    h:array[-5000..10000,0..5000]of longint;
    n,ans:longint;

function gcd(a,b:longint):longint;
begin
  if b=0 then exit(a);
  exit(gcd(b,a mod b));
end;

procedure prepare;
var i:longint;
begin
  for i:=1 to 10000 do
    h[i,0]:=0;
end;

procedure init;
var i:longint;
begin
  read(n);
  for i:=1 to n do
   begin
     read(x[i]);read(y[i]);
     inc(h[x[i],0]);
     h[x[i],h[x[i],0]]:=y[i];
   end;
end;

function test(u,v,p,q:longint):boolean;
var xx,yy,i:longint;
begin
  xx:=x[u]+p-x[v];
  yy:=y[u]+q-y[v];
  for i:=1 to h[xx,0] do
   if h[xx,i]=yy then exit(true);
  exit(false);
end;

procedure cal(u,v,p,q:longint);
var i,j,sq,a,b:longint;
begin
  sq:=(x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]);
  i:=x[u]-x[v]; i:=abs(i);
  j:=y[u]-y[v]; j:=abs(j);
  b:=gcd(i,j)+1;
  i:=p-x[v]; i:=abs(i);
  j:=q-y[v]; j:=abs(j);
  b:=b+gcd(i,j)-1;
  a:=sq+1-b;
  if a+2*b>ans then ans:=a+2*b;
end;

procedure main;
var i,j,p,q,xx,yy:longint;
begin
  ans:=0;
  for i:=1 to n do
    for j:=i+1 to n do
        begin
          p:=x[i]-x[j];
          q:=y[i]-y[j];
          xx:=x[j]+q;
          yy:=y[j]-p;
          if test(i,j,xx,yy) then cal(i,j,xx,yy);
          xx:=x[j]-q;
          yy:=y[j]+p;
          if test(i,j,xx,yy) then cal(i,j,xx,yy);
        end;
  write(ans);
end;

begin
  prepare;
  init;
  main;
end.

最后此题还是A掉了,实践表明随机化的反而还方便些....而正经的二分查找反而过不了数据.....

program mike;
var x,y:array[1..5000]of longint;
    n,ans:longint;
    s,t:array[-10000..10000]of longint;

procedure prepare;
var i:longint;
begin
  s[x[1]]:=1;
  t[x[n]]:=n;
  for i:=1 to n do
    begin
     if (i<>1)and(x[i-1]<>x[i]) then s[x[i]]:=i;
     if (i<>n)and(x[i+1]<>x[i]) then t[x[i]]:=i;
    end;
end;

function find(i,j:longint):boolean;
var k:longint;
begin
  if (i<-10000)or(i>10000)or(j<-10000)or(j>10000) then exit(false);
  if (s[i]=0)or(t[i]=0) then exit(false);
  for k:=s[i] to t[i] do
   if y[k]=j then exit(true);
  exit(false);
end;

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

function gcd(a,b:longint):longint;
begin
  if b=0 then exit(a);
  exit(gcd(b,a mod b));
end;

{function find(i,j:longint):boolean;
var l,r,mid:longint;
begin
  l:=1;r:=n;
  if (i<-10000)or(i>10000)or(j<-10000)or(j>10000) then exit(false);
  while l<=r do
   begin
     mid:=(l+r)shr 1;
     if (x[mid]=i)and(y[mid]=j) then exit(true);
     if (x[mid]>i)or((x[mid]=i)and(y[mid]>j)) then
        r:=mid-1;
     if (x[mid]<i)or((x[mid]=i)and(y[mid]<j)) then
        l:=mid+1;
   end;
  exit(false);
end;   }

procedure init;
var i:longint;
begin
  read(n);
  for i:=1 to n do
   begin
     read(x[i]);read(y[i]);
   end;
  qsort(1,n);
end;

function test(u,v,p,q:longint):boolean;
var xx,yy,i:longint;
begin
  xx:=x[u]+p-x[v];
  yy:=y[u]+q-y[v];
   if find(xx,yy) then exit(true);
  exit(false);
end;

procedure cal(u,v,p,q:longint);
var i,j,sq,a,b:longint;
begin
  sq:=(x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]);
  i:=x[u]-x[v]; i:=abs(i);
  j:=y[u]-y[v]; j:=abs(j);
  b:=gcd(i,j);
  i:=p-x[v]; i:=abs(i);
  j:=q-y[v]; j:=abs(j);
  b:=b+gcd(i,j);
  a:=sq+1-b;
  if a+2*b>ans then ans:=a+2*b;
end;

procedure main;
var i,j,k,p,q,xx,yy,qqq:longint;
begin
  ans:=0;
  for i:=1 to n do
   begin
     qqq:=0;
     for j:=i+1 to n do
        begin
          p:=x[i]-x[j];
          q:=y[i]-y[j];
          xx:=x[j]+q;
          yy:=y[j]-p;
          if find(xx,yy) then
          if test(i,j,xx,yy) then cal(i,j,xx,yy);
          xx:=x[j]-q;
          yy:=y[j]+p;
          if find(xx,yy) then
          if test(i,j,xx,yy) then cal(i,j,xx,yy);
        end;
   end;
  write(ans);
end;

begin
  assign(input,'ss.in');
  reset(input);
  init;
  prepare;
  main;
  close(input);
end.

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

历史上的今天

评论

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

页脚

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