【bzoj1670】[Usaco2006 Oct]Building the Moat护城河的挖掘 凸
发布时间:2020-12-14 02:00:48 所属栏目:大数据 来源:网络整理
导读:裸的凸包啦,第一次写。 #includecstdio#includecstring#includecstdlib#includecmath#includealgorithm#includeiostream#define maxn 5010 using namespace std;struct yts{long long x,y;}a[maxn],s[maxn];long long operator*(yts x,yts y){return x.x*y.
裸的凸包啦,第一次写。
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<algorithm> #include<iostream> #define maxn 5010 using namespace std; struct yts { long long x,y; }a[maxn],s[maxn]; long long operator*(yts x,yts y) { return x.x*y.y-x.y*y.x; } yts operator-(yts x,yts y) { yts ans; ans.x=y.x-x.x;ans.y=y.y-x.y; return ans; } double dis(yts x,yts y) { return sqrt((double)(x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y)); } int n,m; double ans; bool cmp(yts x,yts y) { int t=(x-a[1])*(y-a[1]); if (t==0) return dis(x,a[1])<dis(y,a[1]); return t<0; } void graham() { int t=1; for (int i=2;i<=n;i++) if (a[i].x<a[t].x || (a[i].x==a[t].x && a[i].y<a[t].y)) t=i; swap(a[t],a[1]); sort(a+2,a+n+1,cmp); int top=1; s[top]=a[1]; for (int i=2;i<=n;i++) { while (top>1 && (s[top]-s[top-1])*(a[i]-s[top])>=0) top--; s[++top]=a[i]; } s[top+1]=a[1]; for (int i=1;i<=top;i++) ans+=dis(s[i],s[i+1]); } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y); graham(); printf("%.2lfn",ans); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |