二维凸包

Andrew算法

时间复杂度\(O(nlogn)\)
把所有点以横坐标为第一关键字排序，纵坐标为第二关键字
最小的元素和最大的元素一定在凸包上
从第一个点开始遍历，如果下一个点在栈顶的两个元素所连成直线的左边，那么就入栈
否则如果在右边，说明凸包有更优的方案，上次的点出栈，
并直到新点在栈顶两个点所在的直线的左边为止
至于判断左边还是右边，用叉积

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

const int N=2e5+100;

struct cor {

	double x,y;

}a[N],b[N];

double dist(cor p,cor q) {
	double A=p.x-q.x,B=p.y-q.y;
	return sqrt(A*A+B*B);
}

double cross(cor p,cor r,cor q) {
	double x1=p.x-r.x,y1=p.y-r.y;
	double x2=q.x-r.x,y2=q.y-r.y;
	return (x1*y2)-(x2*y1);
}

bool cmp(cor p,cor q) {
	if(p.x==q.x) return p.y<q.y;
	return p.x<q.x;
}

int n,cnt=0;
double ans=0; 
void Andrew() {
	
	sort(a+1,a+n+1,cmp);
	b[++cnt]=a[1];
	for(int i=2;i<=n;i++) {
		
		while(cnt>1&&cross(b[cnt],b[cnt-1],a[i])<=0) cnt--;
		b[++cnt]=a[i];
		
	}
	int t=cnt;
	for(int i=n-1;i>=1;i--) {
		
		while(cnt>t&&cross(b[cnt],b[cnt-1],a[i])<=0) cnt--;
		b[++cnt]=a[i];
		
	}
	
}

int main() {
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%lf%lf",&a[i].x,&a[i].y);
	}
	Andrew();
	for(int i=1;i<cnt;i++) ans+=dist(b[i],b[i+1]);
	ans+=dist(b[cnt],b[1]);
	printf("%.2lf\n",ans);

	return 0;
}