Description:

There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him?
The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line.

There are no more than 100 trees.

Input:

The input contains one or more data sets. At first line of each input data set is number of trees in this data set, it is followed by series of coordinates of the trees. Each coordinate is a positive integer pair, and each integer is less than 32767. Each pair is separated by blank.

Zero at line for number of trees terminates the input for your program.

Output:

The minimal length of the rope. The precision should be 10^-2.

Sample Input:

9
12 7
24 9
30 5
41 9
80 7
50 87
22 9
45 1
50 7
0

Sample Output:

243.06

题目链接

求一个简单凸包，模板题。

先找到基准点(最左下角)，之后将其他点按照极角排序，遍历顶点依次用叉乘判断当前顶点和上一个顶点构成的线段是否在上一个顶点和上上个顶点构成线段的顺时针方向，若是则上一个顶点不属于构成结果的多边形中，若不是则上一个顶点在构成结果的多边形中，最后求和即可。

注意特判一个点以及两个点的情况。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define XDebug(x) cout<<#x<<"="<<x<<endl;
#define ArrayDebug(x,i) cout<<#x<<"["<<i<<"]="<<x[i]<<endl;
#define print(x) out(x);putchar('\n');
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
template <class T>
inline bool read(T &ret) {
	char c;
	int sgn;
	if (c = getchar(), c == EOF) {
		return 0;
	}
	while (c != '-' && (c < '0' || c > '9')) {
		c = getchar();
	}
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0' && c <= '9') {
		ret = ret * 10 + (c - '0');
	}
	ret *= sgn;
	return 1;
}
template <class T>
inline void out(T x) {
	if (x < 0) {
		putchar('-');
		x = -x;
	}
	if (x > 9) {
		out(x / 10);
	}
	putchar(x % 10 + '0');
}

struct Point {
	double x, y;
	Point(double _x = 0.0, double _y = 0.0): x(_x), y(_y) {}
	void input() {
		scanf("%lf%lf", &x, &y);
	}
	void output() {
		printf("%lf %lf", x, y);
	}
	Point operator - (const Point &b) const{
		return Point{x - b.x, y - b.y};
	}
	double operator ^ (const Point &b) const {
		return x * b.y - y * b.x;
	}
};

double PointDis(Point a, Point b) {
	return hypot(a.x - b.x, a.y - b.y);
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n;
	while (read(n) && n) {
		vector<Point> points(n);
		int Basic = 0;
		for (int i = 0; i < n; ++i) {
			points[i].input();
			if (i > 0) {
				if (points[i].y < points[Basic].y || (points[i].y == points[Basic].y && points[i].x < points[Basic].x)) {
					Basic = i;
				}
			}
		}
		if (n == 1) {
			printf("%.2lf\n", 0);
			continue;
		}
		else if (n == 2) {
			printf("%.2lf\n", PointDis(points[0], points[1]));
			continue;
		}
		swap(points[0], points[Basic]);
		sort(points.begin() + 1, points.end(), [&] (const Point &a, const Point &b) {
			double temp = (a - points[0]) ^ (b - points[0]);
			if (temp > 0) {
				return 1;
			}
			else if (!temp && PointDis(a, points[0]) < PointDis(a, points[0])) {
				return 1;
			}
			return 0;
		});
		vector<Point> Stack;
		Stack.pb(points[0]); Stack.pb(points[1]);
		for (int i = 2; i < n; ++i) {
			while (Stack.size() >= 2 && ((Stack.back() - Stack[Stack.size() - 2]) ^ (points[i] - Stack[Stack.size() - 2])) <= 0) {
				Stack.pop_back();
			}
			Stack.pb(points[i]);
		}
		Stack.pb(points[0]);
		double ans = 0;
		for (int i = 1; i < int(Stack.size()); ++i) {
			ans += PointDis(Stack[i], Stack[i - 1]);
		}
		printf("%.2lf\n", ans);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}