p3829专题

P3829 [SHOI2012] 信用卡凸包 题解

解题思路 不难的题,但是细节有亿点多…… 观察三组样例不难发现,我们可以把所有的信用卡的圆角去掉,变成一个长 b − 2 ⋅ r b-2\cdot r b−2⋅r,宽 a − 2 ⋅ r a-2\cdot r a−2⋅r 的矩形。考虑将这个矩形的四个顶点加入一个点集中,然后求凸包,答案即为这个凸包的周长加上一个半径为 r r r 的 ⚪ 的周长。 那么怎么求出凸包周长呢?显然的,我们在