ZSH_ZSH的博客

博客

The 3rd Universal Cup. Stage 0: Trial Contest L 题解

2024-06-11 16:39:14 By ZSH_ZSH

又名: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

当红色三角形的顶点位于一条对角线上时,可能的解是两两拼成正方形的一半。

注意到除了这两种情况之外没有别的解,判掉即可。

ZSH_ZSH Avatar