题目传送门
今天突然想学习一下凸包，没想到还挺简单的
这是一道凸包模板题目
利用atan2进行极角排序
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;typedef long long ll;
const int maxn=10000+100;
const int INF=0x3f3f3f3f;struct Node{int x,y;
}node[maxn],tubao[maxn];
int top;
int n;inline bool cmp(Node a,Node b){double A=atan2(a.y-node[1].y,a.x-node[1].x);double B=atan2(b.y-node[1].y,b.x-node[1].x);if(A==B) return a.x<b.x;return A<B;
}inline ll cross(Node a,Node b,Node c){return (ll)(b.x-a.x)*(c.y-a.y)-(ll)(c.x-a.x)*(b.y-a.y);
} void getTuBao(){node[0]=(Node){INF,INF};int tmp;for(int i=1;i<=n;i++){if(node[i].y<node[0].y || (node[i].y==node[0].y && node[i].x<node[0].x)) node[0]=node[i],tmp=i;}swap(node[1],node[tmp]);sort(node+2,node+1+n,cmp);tubao[0]=node[1];tubao[1]=node[2];top=1;for(int i=3;i<=n;i++){while(top&&cross(tubao[top-1],tubao[top],node[i])<=0) top--;tubao[++top]=node[i];}
} double Dis(Node a,Node b){return sqrt((ll)(a.x-b.x)*(a.x-b.x)+(ll)(a.y-b.y)*(a.y-b.y));
}void getDis(){double dis=0;if(top==0) dis=0;else if(top==1) dis=Dis(tubao[0],tubao[1]);else{tubao[++top]=tubao[0];for(int i=0;i<top;i++) dis+=Dis(tubao[i],tubao[i+1]);}printf("%.2f\n",dis);
}int main(){while(scanf("%d",&n)==1&&n){for(int i=1;i<=n;i++) scanf("%d%d",&node[i].x,&node[i].y);getTuBao();getDis(); }
}利用叉积进行极角排序
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;typedef long long ll;
const int maxn=10000+100;
const int INF=0x3f3f3f3f;struct Node{int x,y;
}node[maxn],tubao[maxn];
int top;
int n;inline ll cross(Node a,Node b,Node c){return (ll)(b.x-a.x)*(c.y-a.y)-(ll)(c.x-a.x)*(b.y-a.y);
} inline bool cmp(Node a,Node b){if(cross(node[1],a,b)==0) return a.x<b.x;return cross(node[1],a,b)>0;
}void getTuBao(){node[0]=(Node){INF,INF};int tmp;for(int i=1;i<=n;i++){if(node[i].y<node[0].y || (node[i].y==node[0].y && node[i].x<node[0].x)) node[0]=node[i],tmp=i;}swap(node[1],node[tmp]);sort(node+2,node+1+n,cmp);tubao[0]=node[1];tubao[1]=node[2];top=1;for(int i=3;i<=n;i++){while(top&&cross(tubao[top-1],tubao[top],node[i])<=0) top--;tubao[++top]=node[i];}
} double Dis(Node a,Node b){return sqrt((ll)(a.x-b.x)*(a.x-b.x)+(ll)(a.y-b.y)*(a.y-b.y));
}void getDis(){double dis=0;if(top==0) dis=0;else if(top==1) dis=Dis(tubao[0],tubao[1]);else{tubao[++top]=tubao[0];for(int i=0;i<top;i++) dis+=Dis(tubao[i],tubao[i+1]);}printf("%.2f\n",dis);
}int main(){while(scanf("%d",&n)==1&&n){for(int i=1;i<=n;i++) scanf("%d%d",&node[i].x,&node[i].y);getTuBao();getDis(); }
}