hdu1392 Surround the Trees 【简单凸包】

题意：

给你n个点，求将所有点都围起来的凸包的周长

题目链接：传送门

关于凸包的原理：传送门

AC_code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1e5 + 10, M = 30005, mod = 1e9 + 7, inf = 0x3f3f3f3f;

struct Point {
	double x, y;
	Point (double x = 0, double y = 0):x(x),y(y) {}
	Point operator + (const Point &b) {
		return Point(x+b.x, y+b.y);
	}
	Point operator - (const Point &b) {
		return Point(x-b.x,y-b.y);
	}
} p[N],res[N];

double dis(Point aa, Point bb) {
	return sqrt((aa.x - bb.x) * (aa.x - bb.x) + (aa.y - bb.y) * (aa.y - bb.y));
}
double dot(Point aa, Point bb) {
	return aa.x * bb.y - bb.x * aa.y;
}
bool cmp(Point aa, Point bb) {
	if(aa.y == bb.y) {
		return aa.x < bb.x;
	} else {
		return aa.y < bb.y;
	}
}

int get(Point* p, int n, Point* res) {
	sort(p+1, p+1+n, cmp);
	res[1] = p[1];
	res[2] = p[2];
	int top = 2, len;
	for(int i = 3; i <= n; i++) {
		while(top >= 2 && dot((p[i] - res[top - 1]), (res[top] - res[top-1])) >= 0) {
			top--;
		}
		res[++top] = p[i];
	}
	len = top;
	for(int i = n; i >= 1; i--) {
		while(top != len && dot((p[i] - res[top - 1]), (res[top] - res[top-1])) >= 0) {
			top--;
		}
		res[++top] = p[i];
	}
	return top;
}


int main() {
	int n;
	while(~scanf("%d", &n)) {
		if(n == 0) {
			break;
		}
		for(int i = 1; i <= n; i++) {
			scanf("%lf%lf", &p[i].x, &p[i].y);
		}
		if(n == 1) {
			printf("0.00\n");
			continue;
		} else if(n == 2) {
			printf("%.2lf\n",dis(p[1], p[2]));
			continue;
		}

		int m = get(p, n, res);
		double tot = 0;
		for(int i = 2; i <= m ; i++) {
			tot += dis(res[i-1], res[i]);
		}
		printf("%.2lf\n", tot);
	}
	return 0;
}