直接上模板，不过模板还不够精练，以后再慢慢优化
/*
* hdu1392/win.cpp
* Created on: 2011-10-22
* Author : ben
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
const int MAXN = 110;
const double eps = 1e-8;
#define zero(x) (((x)>0?(x):-(x))<eps)
typedef double typec;
typedef struct {
typec x;
typec y;
} MyPoint;
inline double xmult(MyPoint p1, MyPoint p2, MyPoint p0) {
return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
MyPoint p1, p2;
inline bool graham_less(const MyPoint& a, const MyPoint& b) {
double ret = xmult(a, b, p1);
if (zero(ret)) {
return xmult(a, b, p2) < 0;
} else {
return ret < 0;
}
}
void _graham(int n, MyPoint* p, int& s, MyPoint* ch) {
int i, k = 0;
for (p1 = p2 = p[0], i = 1; i < n; p2.x += p[i].x, p2.y += p[i].y, i++) {
if (p1.y - p[i].y > eps || (zero(p1.y - p[i].y) && p1.x > p[i].x)) {
p1 = p[k = i];
}
}
p2.x /= n, p2.y /= n;
p[k] = p[0], p[0] = p1;
sort(p + 1, p + n, graham_less);
for (ch[0] = p[0], ch[1] = p[1], ch[2] = p[2], s = i = 3; i < n; ch[s++] =
p[i++]) {
for (; s > 2 && xmult(ch[s - 2], p[i], ch[s - 1]) < -eps; s--) {
;
}
}
}
//构造凸包接口函数,传入原始点集大小n,点集p(p原有顺序被打乱!)
//返回凸包大小,凸包的点在convex中
//参数maxsize为1包含共线点,为0不包含共线点,缺省为1
//参数clockwise为1顺时针构造,为0逆时针构造,缺省为1
//在输入仅有若干共线点时算法不稳定,可能有此类情况请另行处理!
//不能去掉点集中重合的点
int graham(int n, MyPoint* p, MyPoint* convex, int maxsize = 1, int dir = 1) {
MyPoint* temp = new MyPoint[n];
int s, i;
_graham(n, p, s, temp);
convex[0] = temp[0], n = 1, i = (dir ? 1 : (s - 1));
for (; dir ? (i < s) : i; i += (dir ? 1 : -1) ) {
if (maxsize || !zero(xmult(temp[i-1],temp[i],temp[(i+1)%s]))) {
convex[n++]=temp[i];
}
}
delete[] temp;
return n;
}
inline double mydistance(MyPoint &p1, MyPoint &p2) {
double deltax = p1.x - p2.x;
double deltay = p1.y - p2.y;
return sqrt(deltax * deltax + deltay * deltay);
}
MyPoint points[MAXN], tubao[MAXN];
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int n, m;
double ans;
while (scanf("%d", &n) == 1 && n > 0) {
for (int i = 0; i < n; i++) {
scanf("%lf%lf", &points[i].x, &points[i].y);
}
ans = 0;
if (n == 2) {
ans = mydistance(points[0], points[1]);
} else {
m = graham(n, points, tubao);
for (int i = 0; i < m; i++) {
ans += mydistance(tubao[i], tubao[(i + 1) % m]);
}
}
printf("%.2f\n", ans);
}
return 0;
}