题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6325
注意观察每次移动的花费xi yj - xj yi,这是一个叉积。题目希望花费的负值最大,也就是所有的叉积和尽可能小。贪心考虑,我们需要让移动路线尽可能「上凸」,这样可以向顺时针转动的角度也会尽可能的大。于是维护一个上凸包即可。注意字典序的处理方式,拓展凸包时,如果在一个方向上遇到字典序较大的点,则不要弹出栈里的当前点。
1 |
|
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6325
注意观察每次移动的花费xi yj - xj yi,这是一个叉积。题目希望花费的负值最大,也就是所有的叉积和尽可能小。贪心考虑,我们需要让移动路线尽可能「上凸」,这样可以向顺时针转动的角度也会尽可能的大。于是维护一个上凸包即可。注意字典序的处理方式,拓展凸包时,如果在一个方向上遇到字典序较大的点,则不要弹出栈里的当前点。
1 | #include <cstdio> |