题目大意:输入N个点坐标,求凸包周长加上一个以M为半径的圆的周长。
解题思路:首先解决凸包,
解决凸包的首要问题,是算法,这里用Graham_scan扫描算法。
第一步:存入点,开辟一个数组;
第二步:在输入点之后的同时,进行在保证y坐标最小的情况下,x坐标最小的点的寻找。用个if判断。记下该点的位置i;
第三步:已经跳出输入的循环,进行一次交换,最小y,x点与存点数组的第一个元素下标为0的互换点值。
第四步:排序:这里使用快排函数:首先第一步:建立比较函数:比较函数的建立需要判断函数,即叉乘的判断。叉乘的判断也就是极角大小的判断
第二步:进行排序;
第五步:建立一个点栈,用以存凸包上的点。
第六步:根据极角的值依次将排好序的数组下标为0,1,2的元素入栈。
第七步:从存点数组下标为3的点开始判断,这里的判断是根据栈的顶端两个元素和存点数组的第i个元素进行的判断。i是for循环的。这个判断的意义在于判断这三个点所形成的角是不是大于180度,小于180度继续扫描下一个点,若大于180度说明第二个点一定在凸包内部,然后我们暂时停止扫描下一个点,将指向栈顶的元素top减一,继续执行这个判断。直到三点所形成的角小于180度。
第八步:第七步结束之后凸包上的点就都存在了栈里面了。然后我们就开始计算凸包的周长,用一个函数即可。
第九步:输出凸包周长和以M为半径的圆的周长的相加总和就是题目所求的答案了。
首先解释下这个提交后的运行时间Time为0MS的蕴意,我连续提交过20次,第一次是0MS,第二次是16MS,第三次32,第四次16,第五次32,第六次16,第七次0,然后就是这么一直的下去,差不多就都是这三种情况0,16,32。代码是相同的。内存的话,你把结构体里的int 改成short可以减少8K的 开销。
Source Code Problem: 1113 User: 201141919106 Memory: 208K Time: 0MS Language: C++ Result: Accepted Source Code #include <stdio.h> #include <stdlib.h> #include <math.h> #define MAX 1001 #define Pi 3.14159265 typedef struct { int x,y; }Point; Point PointSet[MAX];//第一步 Point ch[MAX];//第五步 int multiply(Point p1,Point p2,Point p0)//判断极角大小 { return (p1.y-p0.y)*(p2.x-p0.x)-(p2.y-p0.y)*(p1.x-p0.x); } int multi(Point p1,Point p2,Point p3)//判断三点组成的角度 { return (p3.y-p2.y)*(p2.x-p1.x)-(p2.y-p1.y)*(p3.x-p2.x); } int dis(Point p1,Point p2) { return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y); } int cmp(const void* pp,const void* qq)//排序判断条件 { Point p1,p2; p1=*(Point*) pp; p2=*(Point*) qq; if(multiply(p1,p2,PointSet[0])>0) return 1; else if(multiply(p1,p2,PointSet[0])==0 && dis(p1,PointSet[0])>dis(p2,PointSet[0]))//极角相等的情况下,要距离最远的那个。 return 1; return -1; } double Graham_scan(int n,int m) { int i,j,k=0; int top=2; double len=0; ch[0]=PointSet[0];//第六步 ch[1]=PointSet[1]; ch[2]=PointSet[2]; for (i=3; i<n; i++)//第七步 { while(multi(ch[top-1],ch[top],PointSet[i])<0) top--; ch[++top]=PointSet[i]; } for(i=1; i<=top; i++)//第八步,因为进过这个循环后,下标为0和top的点之间的距离为算进去,所以有了下面那个加法 { len+=sqrt((double)dis(ch[i],ch[i-1])); } len+=2*m*Pi+sqrt((double)dis(ch[0],ch[top]));//第九步 return len; } int main() { int n,m,i,min; Point minPoint; scanf("%d%d",&n,&m); for(i=0; i<n; i++) { scanf("%d%d",&PointSet[i].x,&PointSet[i].y);//第二步 if(minPoint.x>PointSet[i].x) { minPoint=PointSet[i]; min=i; } else if(minPoint.x==PointSet[i].x && minPoint.y>PointSet[i].y) { minPoint=PointSet[i]; min=i; } } PointSet[min]=PointSet[0];PointSet[0]=minPoint;//第三步 qsort(PointSet+1,n-1,sizeof(PointSet[0]),cmp);//第四步--- printf("%.lf\n",Graham_scan(n,m));//输出 return 0; }