废话不多说,直接上模板
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {
int x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0', c=getchar();
return x;
}
const int maxn = 5e3+3;
const int mod = 1e9+7;
const double eps = 1e-9;
struct P{
int x, y;
}p[maxn], s[maxn];
inline P operator - (P a, P b) {
return (P){a.x-b.x,a.y-b.y};
}
inline ll X(P a, P b) {
return a.x*b.y-a.y*b.x;
}
inline double dis(P a, P b) {
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline bool operator < (P a, P b) {
ll t=X(a-p[1],b-p[1]);
if(t==0) return dis(p[1],a)<dis(p[1],b);
return t>0;
}
int N, top; //top为凸包顶点数
double ans; // ans为凸包周长
void graham() {
int t=1;
for(int i=2; i<=N; ++i)
if(p[i].y<p[t].y||(p[i].y==p[t].y&&p[i].x<p[t].x)) t=i;
swap(p[1],p[t]);
sort(p+2,p+N+1); //将剩下的点按照极角排序!否则就是O(n^2)的算法啦
s[++top]=p[1];
s[++top]=p[2]; //关键在于先找到头两个点
for(int i=3; i<=N; ++i) {
while(X(s[top]-s[top-1],p[i]-s[top-1])<=0) top--; //常用的一个操作,千万要熟悉!
s[++top]=p[i];
}
s[top+1]=p[1];
for(int i=1; i<=top; ++i) ans+=dis(s[i],s[i+1]);
}
int main() {
//ios::sync_with_stdio(false);
N=read();
for(int i=1; i<=N; ++i) p[i]=(P){read(),read()}; //从1开始记录
if(N==1) { //千万记住这两个特判!
printf("0.00\n");
return 0;
}
if(N==2) {
printf("%.2f\n", dis(p[0],p[1]));
return 0;
}
graham();
printf("%.2f\n", ans);
}