【计算几何】【凸包】bzoj1670 [Usaco2006 Oct]Building the Moat护城河的挖掘

时间:2023-03-09 23:16:28
【计算几何】【凸包】bzoj1670 [Usaco2006 Oct]Building the Moat护城河的挖掘
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 5001
struct Point{int x,y;}p[N],bao[N];
bool operator < (Point a,Point b){return a.x!=b.x?a.x<b.x:a.y<b.y;}
typedef long long ll;
typedef Point Vector;
Vector operator - (Point a,Point b){return (Vector){a.x-b.x,a.y-b.y};}
ll Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
double sqr(int x){return (double)x*(double)x;}
double dis(Point a,Point b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
int n,en;
double ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d%d",&p[i].x,&p[i].y);
sort(p+1,p+1+n);
for(int i=1;i<=n;++i)
{
while(en>1&&Cross(bao[en]-bao[en-1],p[i]-bao[en])<=0)
--en;
bao[++en]=p[i];
}
int half=en;
for(int i=n-1;i;--i)
{
while(en>half&&Cross(bao[en]-bao[en-1],p[i]-bao[en])<=0)
--en;
bao[++en]=p[i];
}
for(int i=2;i<=en;++i)
ans+=dis(bao[i],bao[i-1]);
printf("%.2f\n",ans+dis(bao[1],bao[en]));
return 0;
}