记录编号	406244	评测结果	AAAAAAAA
题目名称	圈奶牛	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.031 s
提交时间	2017-05-18 10:44:09	内存使用	0.58 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

const int MAXN = 1e4 + 10;
struct DATA{ 
	double x, y;
	double cos;

	DATA(double& a, double& b){ 
		x = a, y = b;
		cos = 0;
	}
	DATA(){;}

	bool operator < (const DATA& a) const { 
		return a.cos < cos;
	}
};

inline double get_cos(const DATA& a);
inline bool cmp(const DATA& a, const DATA& b);
inline bool check(int a);
inline double get_len(int a, int b);

int N;
DATA data[MAXN];
DATA tmp;
int stack[MAXN], top;
double ans;

int main(){ 
#ifndef LOCAL
	freopen("fc.in", "r", stdin);
	freopen("fc.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	scanf("%d", &N);

	double x, y;
	scanf("%lf%lf", &x, &y);
	*data = DATA(x, y);

	for(int i = 1; i < N; ++i){ 
		scanf("%lf%lf", &x, &y);
		if(cmp(tmp = DATA(x, y), *data)){ 
			data[i] = *data;
			*data = tmp;
		}
		else data[i] = tmp;
	}

	for(int i = 1; i < N; ++i) data[i].cos = get_cos(data[i]);

	sort(data + 1, data + N);
	data[N] = *data;

	stack[top++] = 0, stack[top++] = 1;
	for(int i = 2; i < N; ++i){ 
		stack[top++] = i;
		while(check(i + 1)) --top;
	}

	//for(int i = 0; i < top; ++i) printf("%d ", stack[i]);
	stack[top++] = N;

	for(int i = 1; i < top; ++i){ 
		ans += get_len(stack[i - 1], stack[i]);
	}

	printf("%.2lf\n", ans);

	return 0;
}

inline bool cmp(const DATA& a, const DATA& b){ 
	if(a.y != b.y) return a.y < b.y;
	return a.x < b.x;
}

inline double get_cos(const DATA& a){ 
	static double dx, dy, dz;
	dx = a.x - data->x;
	dy = a.y - data->y;
	dz = sqrt(dx * dx + dy * dy);
	return dx / dz;
}

inline bool check(int a){ 
	static double x1, y1, x2, y2;
	static int b, c;
	b = stack[top - 1];
	c = stack[top - 2];
	x1 = data[a].x - data[b].x;
	y1 = data[a].y - data[b].y;
	x2 = data[c].x - data[b].x;
	y2 = data[c].y - data[b].y;

	return x2 * y1 - x1 * y2 > 0;
}

inline double get_len(int a, int b){ 
	static double dx, dy;
	dx = data[a].x - data[b].x;
	dy = data[a].y - data[b].y;
	return sqrt(dx * dx + dy * dy);
}