记录编号	433676	评测结果	AAAAAAAA
题目名称	圈奶牛	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2017-08-05 19:11:41	内存使用	0.51 MiB

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

const int MAXN=10010;
const double epsilon=1e-8;

struct Point{
	double x;
	double y;
	Point(double x=0,double y=0){
		this->x=x;
		this->y=y;
	}
	double Cross(const Point& opt){
		return this->x*opt.y-this->y*opt.x;
	}
	double Dot(const Point& opt){
		return this->x*opt.x+this->y*opt.y;
	}
	double EuculidDistance(const Point& opt){
		return sqrt((this->x-opt.x)*(this->x-opt.x)+(this->y-opt.y)*(this->y-opt.y));
	}
	bool operator<(const Point& opt)const{
		return fabs(this->x-opt.x)<epsilon?this->y-opt.y<(-epsilon):this->x-opt.x<(-epsilon);
	}
	Point operator-(const Point& opt){
		return Point(this->x-opt.x,this->y-opt.y);
	}
}P[MAXN];

int s[MAXN],top,n;
bool visited[MAXN];
std::vector<Point> convex;

int main(){
	freopen("fc.in","r",stdin);
	freopen("fc.out","w",stdout);
	double ans=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%lf%lf",&P[i].x,&P[i].y);
	}
	std::sort(P,P+n);
	s[0]=0;
	s[1]=1;
	top=2;
	for(int i=2;i<n;i++){
		while(top>1&&(P[i]-P[s[top-1]]).Cross(P[s[top-2]]-P[s[top-1]])<epsilon)
			top--;
		s[top++]=i;
	}
	for(int i=0;i<top;i++){
		visited[s[i]]=true;
		convex.push_back(P[s[i]]);
	}
	s[0]=n-1;
	s[1]=n-2;
	top=2;
	for(int i=n-3;i>=0;i--){
		while(top>1&&(P[s[top-2]]-P[s[top-1]]).Cross(P[i]-P[s[top-1]])>epsilon)
			top--;
		s[top++]=i;
	}
	for(int i=0;i<top;i++){
		if(!visited[s[i]])
			convex.push_back(P[s[i]]);
	}
	for (std::vector<Point>::iterator i = convex.begin(); i != convex.end(); ++i){
		if(i+1!=convex.end())
			ans+=i->EuculidDistance(*(i+1));
		else
			ans+=i->EuculidDistance(*convex.begin());
	}
	printf("%.2lf\n",ans);
	return 0;
}