又名:hos_lyric 代码复读。
先介绍一个神秘函数 vector<Pt> glue(vector<Pt> ps, const vector<Double> &as, int z)
: 维护一个不知道啥时针方向的严格凸包 ps
,尝试把一个三角形粘在凸包的 (ps[0],ps[n-1])
这条边上。如果粘上之后还能构成严格凸包就返回这个凸包。z
表示三角形是顺时针粘还是逆时针粘。
有了这个 glue 之后,就有了一个爆搜做法:硬搜,维护当前凸包,遍历各种姿势把新三角形塞进去。塞满之后看是不是正方形。
然后我们来分类讨论长啥样的正方形是 glue 不出来的。注意到最终拼成的正方形,一定有至少一条边被某个三角形完整覆盖,不然就寄了。我们枚举这个三角形长啥样。
case 1
发现只有下面这种情况 glue 不出来:
判一判即可。
case 2
白色等腰梯形一定能被 glue 出来,再 glue 个红色的就赢了,下一位。
case 3
先 glue 一个白色三角形,再 glue 个红色的,再 glue 下一个白色三角形,下一位。
case 4
case 4.1
注意到四个三角形交于一点是一组可能合法的解。
case 4.2
当红色三角形的顶点位于一条对角线上时,可能的解是两两拼成正方形的一半。
注意到除了这两种情况之外没有别的解,判掉即可。