链接
模板一
上下利用斜率求凸包然后合并。
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
const double eps=1e-10,inf=0x3f3f3f3f3f3f3f3f;
int n,stak[N],top;
struct point {
double x,y;
}a[N];
bool cmp(point a,point b) {
return a.x==b.x?a.y<b.y:a.x<b.x;
}
double dis(point a,point b) {
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double get_k(point a,point b) {
return a.x==b.x?inf:(a.y-b.y)/(a.x-b.x);
}
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+1+n,cmp);
for(int i=1;i<=n;++i) {
while(top>=2&&get_k(a[stak[top-1]],a[stak[top]])<get_k(a[stak[top]],a[i])) top--;
stak[++top]=i;
}
double ans=0;
for(int i=1;i<top;++i) ans+=dis(a[stak[i]],a[stak[i+1]]);
top=0;
for(int i=n;i>=1;--i) {
while(top>=2&&get_k(a[stak[top-1]],a[stak[top]])<get_k(a[stak[top]],a[i])) top--;
stak[++top]=i;
}
for(int i=1;i<top;++i) ans+=dis(a[stak[i]],a[stak[i+1]]);
printf("%.2lf",ans);
return 0;
}
模板2
Graham算法
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+6;
const double eps=1e-10;
struct point {
double x,y;
}P[N],tmp[N];
point operator - (point a,point b) {
return (point){a.x-b.x,a.y-b.y};
}
point operator + (point a,point b) {
return (point){a.x+b.x,a.y+b.y};
}
double operator * (point a,point b) {
return a.x*b.y-a.y*b.x;
}
int n,stak[N],top;
double dis(point a,point b) {
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool judge_onleft(int p0,int p1,int p2) {
double s=(P[p1]-P[p0])*(P[p2]-P[p0]);
return s<0||((s==0&&dis(P[p1],P[p0]))>=dis(P[p2],P[p0]));
}
bool cmp(point a,point b) {
double s=(a-P[1])*(b-P[1]);
return s<0||(s==0&&dis(a,P[1])>=dis(b,P[1]));
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lf%lf",&P[i].x,&P[i].y);
int First=1;
for(int i=2;i<=n;++i)
if(P[i].x<P[First].x||(P[i].x==P[First].x&&P[i].y<P[First].y)) First=i;
swap(P[First],P[1]);
sort(P+2,P+1+n,cmp);
P[n+1]=P[1];
stak[1]=1,stak[2]=2;
top=2;
for(int i=3;i<=n+1;++i) {
while(top>1&&judge_onleft(stak[top-1],i,stak[top])) top--;
stak[++top]=i;
}
top--;
double ans=0;
for(int i=1;i<top;++i) ans+=sqrt(dis(P[stak[i]],P[stak[i+1]]));
ans+=sqrt(dis(P[stak[top]],P[stak[1]]));
printf("%.2lf",ans);
return 0;
}