凸包
由于 \(Andrew\) 算法较快，所以主要介绍 \(Andrew\) 的实现方式
我们把输入按照 \(x\) 为第一关键字，\(y\) 为第二关键字进行从小到大排序，保证了 \(1\) 和 \(n\) 两个端点把凸包分成了两个部分(称为凸壳)，从 \(1\) 遍历到 \(n\) 再从 \(n\) 遍历到 \(1\) ,把遍历到的点压入栈，使用叉积可以判断栈中点的相对位置，使栈中点只能向左偏离，这样就能找到凸包。
code
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n;
int stu[100010],tot;
bool v[100010];
double ans;
struct node{
double x,y;
}a[100010];
bool cmp(node x,node y){
if(x.x!=y.x) return x.x<y.x;
return x.y<y.y;
}
bool check(){
double a1=a[stu[tot]].x-a[stu[tot-2]].x;
double b1=a[stu[tot]].y-a[stu[tot-2]].y;
double a2=a[stu[tot-1]].x-a[stu[tot-2]].x;
double b2=a[stu[tot-1]].y-a[stu[tot-2]].y;
double an=(a1*b2)-(a2*b1);
if(an>=0) return 0;
return 1;
}
double dis(int x,int y){
return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%lf",&a[i].x,&a[i].y);
}
sort(a+1,a+n+1,cmp);
stu[++tot]=1;
stu[++tot]=2;
for(int i=3;i<=n;i++){
stu[++tot]=i;
while(tot!=2&&!check()){
stu[tot-1]=stu[tot];
tot--;
}
}
for(int i=2;i<=tot;i++){
ans+=dis(stu[i],stu[i-1]);
v[stu[i]]=1;
}
tot=0;
stu[++tot]=n;
stu[++tot]=n-1;
for(int i=n-2;i>=1;i--){
if(v[i]) continue;
stu[++tot]=i;
while(tot!=2&&!check()){
stu[tot-1]=stu[tot];
tot--;
}
}
for(int i=2;i<=tot;i++){
ans+=dis(stu[i],stu[i-1]);
}
printf("%.2lf",ans);
return 0;
}