首页 > 小红的悬崖
开通博客写题解
头像 220405118
发表于 2024-01-14 09:33:37
对于悬崖上连续的三个点，它们构成的形状可以分为两类：“<”形（高点与低点的连线不穿过悬崖）与 “>”形。 （高点与低点的连线穿过了悬崖） 对于“>”形，从顶端到达底端的最短路径就是顺着形状走，而对于“<”形状，从顶端到达底端的最短路径可以忽 略中间的点，即顶端到底端的连线。 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 向楼下逐一发射巨大3BM42芒果尾翼稳定脱壳穿甲弹
发表于 2024-02-06 01:33:56
学习Andrew算法后突然想起这一题。 这简直就是为Andrew算法量身订做的模板题。 因为Andrew算法是一半一半求凸包，而这题实际上只需要求右半边的凸包即可。 甚至题目给出的点都是排好序的，我们就不用费力去排序以及求另一半凸包了。 ```#pragma GCC optimize("O3") # 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”