凸包

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 1e5+1;
const db inf = 1e9;

struct P{
	db x,y,k;
	P(db _x=0,db _y=0,db _k=0){x=_x;y=_y;k=_k;}
	friend bool operator < (P a,P b){
		return a.k<b.k;
	}
	friend db operator * (P a,P b){
		return a.x*b.y-a.y*b.x;
	}
	friend P operator - (P a,P b){
		return P(a.x-b.x,a.y-b.y);
	}
}q[N],a[N];

int n;

bool jud(P a,P b,P t){
	return (t-a)*(t-b)>0;
}

db dis(P a,P b){
	P t=a-b;
	return sqrt(t.x*t.x+t.y*t.y);
}

db work(){
	int R=0;
	for(int i=1;i<=3;++i)q[++R]=a[i];
	for(int i=4;i<=n;++i){
		while(R>1&&jud(q[R],q[R-1],a[i]))R--;
		q[++R]=a[i];
	}
	q[R+1]=q[1];
	db ret=0;
	for(int i=1;i<=R;++i)ret+=dis(q[i],q[i+1]);
	return ret;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%lf%lf",&a[i].x,&a[i].y);
 	int now=0;
	a[0].x=a[0].y=inf;
	for(int i=1;i<=n;++i)if(a[i].x<a[now].x||(a[i].x==a[now].x&&a[i].y<a[now].y))now=i;
	swap(a[1],a[now]);
	for(int i=n;i;--i)a[i].x-=a[1].x,a[i].y-=a[1].y;
	for(int i=1;i<=n;++i)a[i].k=atan2(a[i].y,a[i].x);
	sort(a+2,a+n+1);
	printf("%.2lf\n",work());
}