题目：https://www.luogu.org/problem/P3831 一个网格图，横向或纵向走一边用时2，在特定点转向用时1，问从起点到终点用时最短为多少。  Solution： 虽然题目给出一个网格图，但是实际有用的点就是起点，终点和能换乘的点三种点，其余的点都可以忽略。 考虑分层图，第一层为横走向，第二层为纵走向，中间为转向所花的代价。   代码： #include

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