网易 
新闻 LOFTER 邮箱 相册 阅读 图书 有道 摄影 企业邮箱 优惠券 云笔记 闪电邮 邮箱大师 印像派 考拉海购
 
更多
博客 
手机博客 博客搬家 博客VIP服务 发现 小组 风格
 
群博客 博客油菜地 博客话题 博客热点 博客圈子 找朋友
 
登录  
 加关注
   显示下一条  |  关闭
温馨提示！由于新浪微博认证机制调整，您的新浪微博帐号绑定已过期，请重新绑定！立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

导航

 
 
 
 
 

日志

 
 
关于我
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.
  评论这张
 
阅读(54)| 评论(0)

历史上的今天

评论

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

页脚

我的照片书 - 手机博客 - 下载LOFTER APP - 订阅此博客

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