今天这道题，是凸包的模板题，求的就是凸包的周长。先给出题目链接牛圈，
凸包的计算方式其实是十分简单的，首先先把整张图上面最下面的那个点取出来作为起点，易证这个点必然存在于凸包上面。然后对剩下的所有点进行极角排序，就能得到有序的点坐标数组，按照顺时针从小到大排序，接下来的事情是开始扫描遍历这些点。扫描的时候每次都把一个点加入进去，并且与前面的所有已经加入的点进行比较，如果有点的角度小于当前加入的点相对于当前比较的点的角度，那么就退化更新那个点，利用双指针就可以维护。
附上代码：
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<double, double> P; const int maxn = 1e5 + 5; const double eps = 1e-6; const int INF = 1e9 + 7; const double pi = acos(-1); struct node { double x, y; node(double x, double y) : x(x), y(y) {} node() { x = 0, y = 0; } }; node p[maxn]; node ans[maxn]; double xx, yy; double cross(node a, node b, node c) { return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y); } double dis(node a, node b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } bool cmp(node a, node b) { if (atan2(a.y - yy, a.x - xx) != atan2(b.y - yy, b.x - xx)) return (atan2(a.y - yy, a.x - xx)) < (atan2(b.y - yy, b.x - xx)); return a.x < b.x; } int main() { int t; scanf("%d", &t); int i; xx = yy = INF; int ptr=-1; for (i = 0; i < t; i++) { scanf("%lf %lf", &p[i].x, &p[i].y); if(yy>p[i].y) { xx = p[i].x, yy = p[i].y; ptr = i; } } if (t == 1) printf("0.00\n"); else if (t == 2) printf("%.2f\n", dis(p[0], p[1])); else { memset(ans, 0, sizeof(ans)); ans[0] = node(xx, yy); swap(p[ptr], p[0]); sort(p + 1, p + t, cmp); ans[1] = p[1]; int top = 1; for (i = 2; i < t; i++) { while (cross(ans[top - 1], ans[top], p[i]) < eps) top--; ans[++top] = p[i]; } double s = 0; for (i = 1; i <= top; i++) s += dis(ans[i - 1], ans[i]); s += dis(ans[top], p[0]); printf("%.2lf\n", s); } }