感受到了，被几何搞得晕头转向的感觉
凸包应该算是计算几何中比较基础和常规的算法了。
顺着我的思路来，也许自己日后更好复习。前置芝士
首先你需要一堆关于平面向量的芝士
斜率总要会吧首先我们来看一个简单的问题：
一个平面上给你\(n\)个点，计算把\(n\)个点围起来的最小长度。
这是一个很经典的凸包问题。
那么什么是凸包呢？
大概就是题目中所讲述的那样，把给定点包围在内部的最小凸多边形。
怎么求这个东西呢，这里有好几种方法，这里也就随便介绍一下吧。
\(Graham\)扫描法
二话不说，先放图。
这边就是随便给你的散点图了。
\(Graham\)扫描法是怎么做的呢？
首先我们要找到一个\(y\)最小的点，建立一个坐标系。为了方便，我们再给每个点标号。（那个图有点歪）
把其他点都和P6连起来，我们可以把它看成一个个向量。
对极角的定义：一条向量与\(x\)轴正半轴的夹角（滚去学必修4） 如\(∠1\)就是P1的极角啦。（C党的福利：C++有个函数可以求极角\(atan2(y,x)\)可以求出坐标为\((x,y)\)的向量的极角。（额，真香）
这样，把每个点按照极角从小到大排序。
在这幅图上就是\(P1<P2<P3<P4<P5\)
排好序后你就成功的做完了预处理。
接着再求凸包：
我们就从这个最底下的点（即P6）开始。
每次向右延伸。
比如一开始找到P1，连起来
找到P2，再连
找到P3，再连
咦？好像绿色那条边才是正解。 那不就有问题了吗？ 有问题怎么办？ 我们把P2踢掉不就行啦。 好了，\(Graham\)差不多就是这样的，你只要判断你连起来的这些东西是不是凸多边形的一部分。 至于怎么判断，我们暂且不说（等下你就知道了），只要知道一下思路就好了，下面才是我们的重点方法。 \(Andrew\)算法
好了，这才是这里的重点内容。
那上面一大堆是干什么的。\(Andrew\)算法可以说就是\(Graham\)扫描法的改进。 你把上面的思路当成铺垫就是了。 但是，这个铺垫也提供了很好的思路。 好了，不废话了。 想想画个凸多边形是怎么画的。 首先最左边的点和最右边的点肯定要选吧。 假设把最左边的点作为起笔，那不就是绕一圈就好了吗？ 对啊，这就是\(Andrew\)算法。 首先我们把笔尖定在左端点，然后往右画，在向左，最后回到原点。 画出来的轨迹类似一个圆。 类似\(Graham\)扫描法，我们同样要判断这个点能不能被选作为凸多边形的顶点。 然后到了最右端之后，我们再从右边往左扫。 回到最左端后，你就画了一个凸多边形了。好了，重点来了！ 怎么判断要不要选这个点呢？ 也就是说怎么判断选的这些点是不是凸多边形的一部分？ 想想顺着笔画，凸多边形的边都有哪些特点。 看看刚刚这个图 为什么连\(P1-P3\)而不是把\(P1-P2,P2-P3\)给连了？ 很清晰了吧。 就是斜率嘛！ 要是\(P2-P3\)的斜率没有\(P1-P3\)大，那它肯定是凹进去的。 那就没有用啦，踢掉！ 然后一直找，来回一波，就找到了答案了。 从头到尾都可以用栈实现 看到这里，你可能已经会了\(Garham\)扫描法了。 即使这样，\(Andrew\)算法还是更有用的。 不然为什么要改进？ 不过\(Andrew\)算法貌似也说完了。 看到这里，可能还有一个小问题， 如果画圆回来的时候两个点重复使用怎么办？ 这其实是很好证的。 看下面这幅图
如果当前回来的点选择了紫色的右边那条边，那它一定会被左边那条边覆盖掉。 最终会回到原点 这就保证了\(Andrew\)算法的正确性。 结束了？贴一下代码。 代码可能很丑，而且还有很多没用的东西，懒得删了。 #includeusing namespace std;int n;double ans = 0;#define maxn 11000struct spot{ double x,y; bool operator < (const spot &a) const { if(x == a.x) return y < a.y; return x < a.x; } void read() { scanf("%lf%lf", &x, &y); }}a[maxn];#define inf 99999999struct stacks{ int q[maxn],t; void clear(){t = 0;memset(q, 0, sizeof(q));} void push(int x){q[++ t] = x;} int top(){return q[t];} void pop(){-- t;} bool empty(){return t == 0;} int sec_top(){return q[t - 1];}}q;//拒绝STL依赖bool slope(int ax,int b,int c){ return (a[ax].y-a[b].y)*(a[b].x-a[c].x)>(a[ax].x-a[b].x)*(a[b].y-a[c].y);}double dis(spot a,spot b){return sqrt((a.y - b.y) * (a.y - b.y) + (a.x - b.x) * (a.x - b.x));}int main(){ scanf("%d", &n); for(int i = 1;i <= n;i ++) a[i].read(); sort(a + 1,a + n + 1); for(int i = 1;i <= n;i ++) { while(q.t > 1 && slope(i, q.top(), q.sec_top())) q.pop(); q.push(i); } int k = q.t; for(int i = n - 1;i >= 1;i --) { while(q.t > k && slope(i, q.top(), q.sec_top())) q.pop(); q.push(i); } int last = 1; for(int i = 2;i <= q.t;i ++) ans += dis(a[last], a[q.q[i]]),last = q.q[i]; printf("%.2lf", ans);}
最后，忘了说了，这两个算法的复杂度应该都是\(O(nlogn)\)
时间复杂度主要在排序上。