ac1193.pas

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

program tju1193;
const
  maxn=100;
var
  a,b:array[1..maxn+1,0..maxn*2+2]of byte;
  uu,ud,du,dd:array[1..maxn]of byte;
  n,m,i,j,x1,y1,x2,y2,ans:word;
function min(a,b:word):word;
  begin
    if a<b then min:=a else min:=b;
  end;
function max(a,b:word):word;
  begin
    if a>b then max:=a else max:=b;
  end;
procedure dp(mask:byte);
  begin
    fillchar(b,sizeof(b),0);
    fillchar(du,sizeof(du),0);
    fillchar(ud,sizeof(ud),0);
    for i:=n downto 1 do
      for j:=1 to i do
        if a[i,j*2-1] and mask>0 then begin
          if a[i+1,j*2] and mask>0 then
            b[i,j*2-1]:=1+min(b[i+1,j*2-1],b[i+1,j*2+1])
          else
            b[i,j*2-1]:=1;
          if b[i,j*2-1]>du[i] then du[i]:=b[i,j*2-1];
        end;
    for i:=2 to n do
      for j:=1 to i-1 do
        if a[i,j*2] and mask>0 then begin
          if a[i-1,j*2-1] and mask>0 then
            b[i,j*2]:=1+min(b[i-1,j*2-2],b[i-1,j*2])
          else
            b[i,j*2]:=1;
          if b[i,j*2]>ud[i] then ud[i]:=b[i,j*2];
        end;

    for i:=1 to n do uu[i]:=i+1;
    for i:=1 to n do
      if (du[i]>0) and (i<uu[i+du[i]-1]) then uu[i+du[i]-1]:=i;
    uu[n]:=n+1-uu[i];
    for i:=n-1 downto 1 do begin
      uu[i]:=i+1-uu[i];
      if uu[i+1]>uu[i] then uu[i]:=uu[i+1]-1;
      if du[i+1]>du[i] then du[i]:=du[i+1];
    end;

    for i:=2 to n do dd[i]:=i-1;
    for i:=2 to n do
      if (ud[i]>0) and (i>dd[i-ud[i]+1]) then dd[i-ud[i]+1]:=i;
    dec(dd[2]);
    for i:=3 to n do begin
      dec(dd[i],i-1);
      if dd[i-1]>dd[i] then dd[i]:=dd[i-1]-1;
      if ud[i-1]>ud[i] then ud[i]:=ud[i-1];
    end;

    for i:=2 to n do
      ans:=max(ans,sqr(max(uu[i-1],ud[i-1]))+sqr(max(du[i],dd[i])));
  end;
begin
  repeat
    fillchar(a,sizeof(a),0);
    read(n,m);
    for i:=1 to n do
      for j:=1 to i*2-1 do
        a[i,j]:=7;
    for i:=1 to m do begin
      read(x1,y1);dec(a[x1,y1],1);
      x2:=n-(y1-1) shr 1;y2:=x1*2-y1;dec(a[x2,y2],2);
      x1:=n-(y2-1) shr 1;y1:=x2*2-y2;dec(a[x1,y1],4);
    end;
    ans:=0;
    dp(1);
    dp(2);
    dp(4);
    writeln(ans);
  until seekeof;
end.