USACO 5.1.1バンプテンプレート(水平シーケンス)

/*
ID: liaoxg72
PROB: fc
LANG: C++
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;

const int dmax=100000+100;
const double INF=1000000000;
struct node{
	double x,y;
};
struct node a[dmax];
int c[dmax];
double solve(int u,int v){
	double p=(a[u].y-a[v].y),q=(a[u].x-a[v].x);
	if (q==0)
		return 0;
	return p/q;
}
double dist(int u,int v){
	double p=a[u].x-a[v].x,q=a[u].y-a[v].y;
	p*=p,q*=q;
	q+=p;
	q=sqrt(q);
	return q;
}
int cmp(const node &u,const node &v){
	return u.x<v.x;
}

int main(){
	int i,j,k,m,n;
	freopen("fc.in","r",stdin);
	freopen("fc.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%lf%lf",&a[i].x,&a[i].y);
	sort(a+1,a+n+1,cmp);
	int top=0;
	double ans=0;
	c[++top]=1;
	for (i=2;i<=n;i++){
		while (solve(c[top-1],c[top])>solve(c[top],i) && top>1)
			top--;
		c[++top]=i;
	}
	for (i=1;i<top;i++)
		ans+=dist(c[i],c[i+1]);
	memset(c,0,sizeof(c));
	top=1;
	c[top]=1;
	for (i=2;i<=n;i++){
		while (solve(c[top-1],c[top])<solve(c[top],i) && top>1)
			top--;
		c[++top]=i;
	}
	for (i=1;i<top;i++)
		ans+=dist(c[i],c[i+1]);
	printf("%.2lf
",ans);
	return 0;
}