百度一下原來(lái)叫凸包，所以轉(zhuǎn)了一篇博客講的挺清楚的。

/*
ID:jinbo wu
TASK: fc
LANG:C++
*/ 
#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;
int n;
struct node
{double x,y;
}p[maxn],P[maxn];
double X(node A,node B,node C)
{return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
double len(node A,node B)
{return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
bool cmp(node A,node B)
{double pp=X(p[0],A,B);if(pp>0) return true;if(pp<0) return false;return len(p[0],A)<len(p[0],B);
}
int main()
{freopen("fc.in","r",stdin);freopen("fc.out","w",stdout); scanf("%d",&n);for(int i=0;i<n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);for(int i=1;i<n;i++){if(p[0].y>p[i].y)swap(p[0],p[i]);elseif(p[0].y==p[i].y&&p[0].x>p[i].x)swap(p[0],p[i]);} sort(p+1,p+n,cmp);P[0]=p[0];P[1]=p[1];int tot=1;for(int i=2;i<n;i++){while(tot>0&&X(P[tot-1],P[tot],p[i])<=0) tot--;tot++;P[tot]=p[i];}double ans=0;for(int i=0;i<tot;i++)ans+=len(P[i],P[i+1]);ans+=len(P[tot],P[0]);printf("%.2lf\n",ans); 
}

總結(jié)

以上是生活随笔為你收集整理的usaco fencing the cows的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。