记录编号	81400	评测结果	AAAAAAAA
题目名称	圈奶牛	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2013-11-12 22:29:43	内存使用	0.47 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<deque>
#include<cmath>
using namespace std;
class POINT{//可以表示点/向量
public:
	double x,y;
};
POINT operator - (POINT a,POINT b){
	return (POINT){a.x-b.x,a.y-b.y};
}
bool operator < (POINT a,POINT b){//靠下为小,否则靠左为小
	if(a.y<b.y) return true;
	if(a.y>b.y) return false;
	if(a.x<b.x) return true;
	return false;
}
double dist(POINT a,POINT b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double crp(POINT a,POINT b){
	//x1y2-x2y1
	//若叉积>0则b在a的逆时针方向
	return a.x*b.y-b.x*a.y;
}
void swap(POINT &a,POINT &b){
	POINT c;
	c=a,a=b,b=c;
}
const int SIZEN=10001;
POINT p[SIZEN];//放牧点
int n;
deque<POINT> convexhull;
bool cmp(POINT a,POINT b){//以p[1]为视点,b是否在a的严格逆时针方向上
	return crp(a-p[1],b-p[1])>0;
}
bool anticlock(POINT x,POINT a,POINT b){//以x为视点,b是否在a的严格逆时针方向
	return crp(a-x,b-x)>0;
}
void Graham(void){
	sort(p+2,p+1+n,cmp);
	int i;
	convexhull.push_back(p[1]),convexhull.push_back(p[2]);
	//convexhull.push_back(p[3]);
	int last;
	for(i=3;i<=n;i++){
		last=convexhull.size()-1;
		//向左转意味着以倒数第一个为视点,倒数第二个在该点的严格逆时针方向
		while(!anticlock(convexhull[last],p[i],convexhull[last-1])){//以倒数第一个为视点,倒数第二个不在该点的严格逆时针方向
			convexhull.pop_back();
			last--;
		}
		convexhull.push_back(p[i]);
	}
}
void answer(void){
	double sum=0;
	int i;
	for(i=1;i<convexhull.size();i++) sum+=dist(convexhull[i-1],convexhull[i]);
	sum+=dist(convexhull[0],convexhull[convexhull.size()-1]);
	printf("%.2lf\n",sum);
}
void init(void){
	int minpoint=1;
	int i;
	for(i=2;i<=n;i++) if(p[i]<p[minpoint]) minpoint=i;
	swap(p[1],p[minpoint]);
}
void read(void){
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
}
int main(){
	freopen("fc.in","r",stdin);
	freopen("fc.out","w",stdout);
	read();
	init();
	Graham();
	answer();
	//for(int i=1;i<=n;i++) cout<<p[i].x<<" "<<p[i].y<<endl;
	return 0;
}