Codeforces-178E3 人眼识别题

题意

很简单，给一个 0/1 描述的二维图片，求里面有多少个正方形和圆。正方形的边不一定与坐标轴平行。每个点有 20% 的几率变成相反的点。保证人眼可以轻松识别出来。任意两个图形之间的距离不小于 10 像素，任意一个图形的直径不小于 15 像素。

想吐槽么。目测出数据的人要疯了。

Solution

其实我也不会，乱搞吧。

由于每个点 20% 的几率变成颜色相反的点这个条件太可怕了，我们考虑将整个图形模糊一下。一种方法是加权平均数，也就是每个点取相邻点的加权平均数，然后再取个整。权的话，我们可以模仿 高斯模糊 。我取了周围 9 个点，然后将整个图模糊 10 次。

经过模糊处理后，我们得到的图中，不仅有圆/正方形，还有若干个形状未知的小块。小块的处理很简单，题目保证圆/正方形的直径不小于 15 个像素，我们判断如果块的大小小于某个值（我取 200 ），就把这个小块的颜色全部取反。

没有了干扰点了。对于每个块，只需暴力 BFS 出块的大小 n 以及到中心点的最大距离 r ，对于圆我们有 n ~ pi r^2 ，对于正方形我们有 n ~ 2 r^2 ，所以我们取个中，判断 n 与 2.5 r^2 的大小关系即可。

现在是可以过 Codeforces 的数据了= =||，但是 tsinsen 上的数据实在太强，完全过不了 T_T。

常数优化

cin 读入要 2.4s 。坑死爹= =

判断圆和正方形

判面积是一种方法。这种方法比较怕的就是被模糊后的圆角矩形，因为到最远点的距离会减小。这样可以有 90 分。

还可以找中心点到边界最远点的距离与最近点的距离差？调整参数，分界线为 1.33 的话 92 分，1.35 有 94 分，1.37 有 96 分，1.38 和 1.39 有 98 分。

求凸包后再判？感觉也不靠谱啊，很容易损失正方形中间的点。

最后 98 分被卡的那个点应该是判不出正方形与圆吧，高斯模糊还是不错的。