记录编号	433665	评测结果	AAAAAAAA
题目名称	圈奶牛	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2017-08-05 18:59:49	内存使用	0.51 MiB

#include <stdio.h>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#define db double
#define eps 1e-8 
using namespace std;
int n,stack[10005],top;
bool used[10005];
db ans;
struct coordinates{
	   db x,y; 
	   friend bool operator < (coordinates a,coordinates b){
	   	    return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
	   }
	   friend coordinates operator - (coordinates a,coordinates b){
	   	    return (coordinates){a.x-b.x,a.y-b.y}; 
	   }
}pos[10005];
vector<coordinates> Convex;
db quadratic(db x){return x*x;}
db cross_product(coordinates a,coordinates b){return a.x*b.y-a.y*b.x;}
db distanc(coordinates& a,coordinates& b){
return sqrt(quadratic(a.x-b.x)+quadratic(a.y-b.y));}
bool across(coordinates a,coordinates b,coordinates c){return cross_product(b-a,c-a)>eps;}
int main(){
	freopen("fc.in","r",stdin);
	freopen("fc.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lf%lf",&pos[i].x,&pos[i].y);
    stack[0]=0;
    sort(pos+1,pos+1+n);
    stack[++top]=1;
    stack[++top]=2;
    for(int i=3;i<=n;i++){
        while(top>1&&!across(pos[stack[top]],pos[i],pos[stack[top-1]]))
              top--;
        stack[++top]=i;
    }
    for(int i=1;i<=top;i++){
        used[stack[i]]=true;
        Convex.push_back(pos[stack[i]]);
    }
    top=0;
    stack[++top]=n;
    stack[++top]=n-1;
    for(int i=n-2;i>0;i--){
    	while(top>1&&across(pos[stack[top]],pos[stack[top-1]],pos[i]))
    	      top--;
        stack[++top]=i;
	}
	for(int i=1;i<=top;i++)
	    if(!used[stack[i]])
	       Convex.push_back(pos[stack[i]]);
	for(int i=0,s=Convex.size();i<s;i++)
	    ans+=distanc(Convex[i],Convex[(i+1)%s]);    
	printf("%.2lf",ans);
}