AcWing 1401. 围住奶牛
原题链接
中等
作者:
溪染
,
2021-01-20 16:10:47
,
所有人可见
,
阅读 904
#include<bits/stdc++.h>
using namespace std;
struct Point{
double x,y;
Point(){};
Point(double x,double y):x(x),y(y){};
Point operator-(Point b){
return Point(x-b.x,y-b.y);
}
double operator%(Point b){
return x*b.y-y*b.x;//叉乘
}
bool operator<(Point b){
return x<b.x;
}
}p[10005];
int n;
int stk[10005];
bool uers[10005];
double distanc(Point a,Point b)
{
return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
double work()//求凸包
{
int tp=0;
for(int i=1;i<=n;i++){
while(tp>=2&&((p[stk[tp]]-p[stk[tp-1]])%(p[i]-p[stk[tp-1]]))>0)
uers[stk[tp--]]=0;
uers[i]=1;
stk[++tp]=i;
}
uers[1]=0;
for(int i=n;i>=1;i--){
if(uers[i]) continue;
while(tp>=2&&((p[stk[tp]]-p[stk[tp-1]])%(p[i]-p[stk[tp-1]]))>0)
tp--;
stk[++tp]=i;
}
double ans=0;
for(int i=2;i<=tp;i++)
ans+=distanc(p[stk[i]],p[stk[i-1]]);
return ans;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
double x,y;
scanf("%lf%lf",&x,&y);
p[i]=Point(x,y);
}
sort(p+1,p+n+1);
printf("%.2lf",work());
return 0;
}