为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/starry
来自NOCOW
< USACO
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
- 这是USACO Chapter 5 .1中的OI题目Starry Night的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
[编辑] 问题分析
相信这题大多数人都会。 朴素算法即可。先用floodfill找出星座，然后和以前的星座比较，如果相同则标上以前这个星座的号。如果没找到，编号+1，这个星座的编号就是当前编号。 一个优化：将所有的星座的大小（即横向的最大长度和纵向的最大长度）记录一下，比较的时候如果待比较星座的大小无论是否旋转都和当前星座不一样，则直接跳过。
旋转的时候怎么转（转坐标或者直接重新赋图）都行，有了上述优化，程序肯定不会超时。
此题在判断相似的时候可以借鉴transform
除了大小之外还可以记录星座中星的数量。。数量不一样马上可以Pass。。
Another Algorithm: 因为我极暴力的枚举弄了tle,一气之下改用hash随机进行标号。 优化差不多。但是判断相同的时候用的是hash码
可以用最小表示法来优化、
其实这道题可以写的很短，见C++的selfcon2
介绍一种很快又简单的判相似图形的方法。在floodfill时记下每个点的坐标，之后计算任意两点的距离和，判这个距离和是否相等即可。 由于图形的形状只于图形内部点的相互位置关系决定，所以这样的判断是完全正确的。 (路过：貌似不对啊……WA了好几天发现是这种判重方法有问题……)
