C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 504K, 提交时间: 2019-07-06 19:09:53

#include<bits/stdc++.h>
using namespace std;

struct point {
	double x,y;
	point friend operator -(point a,point b) {
		return {a.x-b.x,a.y-b.y};
	}
} p[5005],s[5005];
double dis(point a,point b) {
	point c=a-b;
	return sqrt(c.x*c.x+c.y*c.y);
}
double X(point a,point b) {
	return a.x*b.y-a.y*b.x;
}
int cmp(point a,point b) {
	double x=X(a-p[1],b-p[1]);

	if(x>0) return 1;
	if(x==0&&dis(a,p[1])<dis(b,p[1])) return 1;
	return 0;
}
double multi(point p1,point p2,point p3) {
	return X(p2-p1,p3-p1);
}
int main() {
	int N;
	scanf("%d",&N);
	for(int i=1; i<=N; i++) scanf("%lf %lf", &p[i].x, &p[i].y);
	int k=1;
	for(int i=2; i<=N; i++)
		if(p[i].y<p[k].y||(p[i].y==p[k].y&&p[i].x<p[k].x))k=i;
	swap(p[1],p[k]);

	sort(p+2,p+1+N,cmp);

	s[1]=p[1];
	s[2]=p[2];
	int t=2;
	for(int i=3; i<=N; i++) {
		while(t>=2&&multi(s[t-1],s[t],p[i])<=0) t--;
		s[++t]=p[i];
	}
	double sum=0;
	for(int i=1; i<t; i++) {
		sum+=dis(s[i],s[i+1]);
	}
	printf("%.2lf\n",sum+dis(s[1],s[t]));

	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 500K, 提交时间: 2020-02-26 13:58:48

#include<cstdio>
#include<cmath>
#include<algorithm>
struct P
{
	long long x,y;
 }a[10000];
 bool operator < (P a,P b)
 {
 	return a.x==b.x?a.y<b.y:a.x<b.x;
 }
 bool ek(P u,P a,P b)
 {
 	return (a.x-u.x)*(b.y-u.y)>(b.x-u.x)*(a.y-u.y);
 }
 double dis(P a,P b)
 {
 	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
 	
 }
 int st[10000],top=0,n;
 double sub(bool dir)
 {
 	st[0]=0;top=1;
 	for(int i=1;i<n;i++)
 	{
 		while(top!=1&&(dir^ek(a[st[top-2]],a[st[top-1]],a[i]))) top--;
 		st[top++]=i;
	 }
	 double ans=0;
	 for(int i=1;i<top;i++) ans+=dis(a[st[i]],a[st[i-1]]);
	 return ans;
 }
 int main()
 {
 	scanf("%d",&n);
 	for(int i=0;i<n;i++)
 	scanf("%d%d",&a[i].x,&a[i].y);
 	std::sort(a,a+n);
 	printf("%.2lf",sub(0)+sub(1));
 }