0%

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 分被卡的那个点应该是判不出正方形与圆吧,高斯模糊还是不错的。