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; beginfor 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; begininc(add);//种数++for i:=1 to sum2[p] doans[lastx[p][i],lasty[p][i]]:=add;//把该图形赋值成这个 end; function long(x1,y1,x2,y2:longint):real;//计算两点之间距离 beginexit(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; beginh:=1;t:=1;x[1]:=fx;y[1]:=fy;boo[fx,fy]:=false;repeatfor i:=1 to 8 doif boo[x[t]+z[i,1],y[t]+z[i,2]] thenbegininc(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 dofor j:=1 to h donum[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 doif abs(num[i]-num[sum])<0.0001 then//利用这个定理判断这两个图形全等beginsame(i,sum);have:=true;from:=i;break;end;if not have then new(sum);//在之前没有全等的图形 end; beginreadln(n);readln(m);for i:=1 to m dobeginfor j:=1 to n dobeginread(ch);if ch='1' then boo[i,j]:=true;end;readln;end;for i:=1 to m dofor j:=1 to n doif boo[i,j] thenbfs(i,j);out[0]:='0';//这样输出简单for i:=1 to 26 do out[i]:=chr(i+96);for i:=1 to m dobeginfor j:=1 to n do write(out[ans[i,j]]);//QAQwriteln;end; end.

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

总结

以上是生活随笔为你收集整理的P2749 夜空繁星的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。