标签: 凸包

1 篇文章

P2924 [USACO08DEC]Largest Fence G 题解
题意 题目链接 给定 $n$ 个点,求一个由若干个点连接成的凸多边形,所包含的点数最多,输出点数。 解析 先说解法:将所有边按照 atan2(y,x) 的值排序, 然后枚举凸多边形起点,再遍历排序后的边进行 dp 转移,复杂度为 $O(n^3)$。 大致思路与已有题解相同,但是我在这里想要阐述一个困惑我许久的点:为什么是 atan2 ? 搜索百度百…