P2749 夜空繁星

USACO的搜索，不知道为什么和二维凸包扯上关系QAQ

刚看到这道题时无从下手…貌似很难呀，大概翻了一下题解…发现了一个玄学定理: 每一个点和别的点的距离相加，一样的图形总是一样的

QAQ 前方水题警告

接下来就简单了…

const z:array[1..8,1..2]of -1..1=((1,0),(0,1),(-1,0),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1));
var i,j,k:longint;
    m,n:longint;
    ans:array[0..101,0..101]of longint;
    boo:array[0..101,0..101]of boolean;
    num:array[0..501]of real;
    sum2:array[0..501]of longint;
    x,y:array[0..161]of longint;
    lastx,lasty:array[0..501]of array[0..161]of longint;
    sum,add:longint;
    ch:char;
    out:array[0..26]of char;
procedure same(p,q:longint);//第p个图形和第q个图形全等，且第q个图形在之前出现过
var i:longint;
begin
  for i:=1 to sum2[q] do 
  ans[lastx[q][i],lasty[q][i]]:=ans[lastx[p][1],lasty[p][1]];//把答案赋值成一样的
end;
procedure new(p:longint);//第p个图形在之前没有出现过
var i:longint;
begin
  inc(add);//种数++
  for i:=1 to sum2[p] do
  ans[lastx[p][i],lasty[p][i]]:=add;//把该图形赋值成这个
end;
function long(x1,y1,x2,y2:longint):real;//计算两点之间距离
begin
  exit(sqrt(sqr(x1-x2)+sqr(y1-y2)));
end;
procedure bfs(fx,fy:longint);//BFS最喜欢了，其实dfs也可以
var i,j,k,h,t:longint;
    have:boolean;
    from:longint=0;
begin
  h:=1;
  t:=1;
  x[1]:=fx;
  y[1]:=fy;
  boo[fx,fy]:=false;
  repeat
    for i:=1 to 8 do
    if boo[x[t]+z[i,1],y[t]+z[i,2]] then
    begin
      inc(h);
      x[h]:=x[t]+z[i,1];
      y[h]:=y[t]+z[i,2];
      boo[x[h],y[h]]:=false;
    end;
    inc(t);
  until t>h;
  inc(sum);
  num[sum]:=0;
  for i:=1 to h do
  for j:=1 to h do
  num[sum]:=num[sum]+long(x[i],y[i],x[j],y[j]);//计算出一个点和别的点的距离之和
  lastx[sum]:=x;//把经过的位置保留下来
  lasty[sum]:=y;
  have:=false;
  sum2[sum]:=h;
  for i:=1 to sum-1 do
  if abs(num[i]-num[sum])<0.0001 then//利用这个定理判断这两个图形全等
  begin
  same(i,sum);
  have:=true;
  from:=i;
  break;
  end;
  if not have then new(sum);//在之前没有全等的图形
end;
begin
  readln(n);
  readln(m);
  for i:=1 to m do
  begin
    for j:=1 to n do
    begin
      read(ch);
      if ch='1' then boo[i,j]:=true;
    end;
    readln;
  end;
  for i:=1 to m do
  for j:=1 to n do
  if boo[i,j] then
  bfs(i,j);
  out[0]:='0';//这样输出简单
  for i:=1 to 26 do out[i]:=chr(i+96);
  for i:=1 to m do
  begin
    for j:=1 to n do write(out[ans[i,j]]);//QAQ
    writeln;
  end;
end.
           

偶尔背一些定理对于做题还是有好处的QAQ