HDOJ 1348 基本二维凸包问题

本文主要是介绍HDOJ 1348 基本二维凸包问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这次写的凸包用的是Graham scan算法

就数据结构上只是简单地运用了一个栈

#include<stdio.h>
#include<cmath>
#include<algorithm>
//#define LOCAL
using namespace std;
const int max1=1000;
typedef struct point
{int x;int y;
}point;
int cp(point a,point b,point c)
{c.x-=a.x;c.y-=a.y;b.x-=a.x;b.y-=a.y;return (b.x*c.y-b.y*c.x)>0;
}
int cmp(point a,point b)
{if(a.y!=b.y) return a.y<b.y;else return a.x<b.x;
}
double len(point a,point b)
{return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y)*1.0);
}
int main()
{#ifdef LOCALfreopen("data.in","r",stdin);#endif // LOCALint t;point a1[max1+5],a2[max1+5];int N,L;int top,mtop,i;double ans;scanf("%d",&t);while(t--){ans=0;scanf("%d%d",&N,&L);for(i=0;i<N;i++) scanf("%d%d",&a1[i].x,&a1[i].y);sort(a1,a1+N,cmp);a2[0]=a1[0];for(i=1,top=0;i<N;i++)//寻找最低点到最高点的右凸包{while(top!=0&&!cp(a2[top-1],a2[top],a1[i]))//在这里如果两条向量在同一条直线上的话(即CP==0)，就将a2【top】弹出//换成距离更远的点top--;a2[++top]=a1[i];}a2[++top]=a1[N-1];mtop=top;//for(i=0;i<top;i++) printf("%d %d\n",a2[i].x,a2[i].y);for(i=N-2;i>=0;i--)//寻找最低点到最高点的左凸包{while(top!=mtop&&!cp(a2[top-1],a2[top],a1[i]))top--;a2[++top]=a1[i];}for(i=0;i<top;i++){ans+=len(a2[i],a2[(i+1)%top]);}ans+=2*L*3.14159;printf("%.0lf\n",ans);//四舍五入就行if(t!=0) printf("\n");}return 0;
}

这篇关于HDOJ 1348 基本二维凸包问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---