acm国际大学生程序设计竞赛计算几何源码

acm国际大学生程序设计竞赛计算几何源码

ID:35712000

大小:217.00 KB

页数:65页

时间:2019-04-13

acm国际大学生程序设计竞赛计算几何源码_第1页
acm国际大学生程序设计竞赛计算几何源码_第2页
acm国际大学生程序设计竞赛计算几何源码_第3页
acm国际大学生程序设计竞赛计算几何源码_第4页
acm国际大学生程序设计竞赛计算几何源码_第5页
资源描述:

《acm国际大学生程序设计竞赛计算几何源码》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、(1)凸包/*凸包cug_1038*/#include#includestructpoint{intx,y;}pp;pointp[100005];intstack[100005],top;intdis(pointa,pointb){return((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}intmulti(pointb,pointc,pointa){return(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.

2、x-a.x);}voidswap(pointp[],ints,intt){pointtmp;tmp=p[s];p[s]=p[t];p[t]=tmp;}intcmp(constvoid*a,constvoid*b){point*c=(point*)a;point*d=(point*)b;doublek=multi(*c,*d,pp);if(k<0)return1;elseif(k==0&&dis(*c,pp)>=dis(*d,pp))return1;elsereturn-1;}voidGraham(poi

3、ntp[],intn,intstack[],int&top){inti,u;u=0;for(i=1;i

4、ack[top-1]])>=0){if(top==0)break;top--;}top++;stack[top]=i;}}intmain(){intca,i,j,n;intarea;scanf("%d",&ca);for(i=1;i<=ca;i++){scanf("%d",&n);for(j=0;j

5、i(p[stack[0]],p[stack[j]],p[stack[j+1]]));}printf("%.1lf",(double)area/2);}return0;}---------------------------------------------------------------------------------------------------------------------(2)判断两条线段是否相交(平行,不平行)boolisIntersected(TPoints1,TPo

6、inte1,TPoints2,TPointe2){//判断线段是否相交//1.快速排斥试验判断以两条线段为对角线的两个矩形是否相交//2.跨立试验if((max(s1.x,e1.x)>=min(s2.x,e2.x))&&(max(s2.x,e2.x)>=min(s1.x,e1.x))&&(max(s1.y,e1.y)>=min(s2.y,e2.y))&&(max(s2.y,e2.y)>=min(s1.y,e1.y))&&(multi(s2,e1,s1)*multi(e1,e2,s1)>=0)&&(mul

7、ti(s1,e2,s2)*multi(e2,e1,s2)>=0))returntrue;returnfalse;}(3)三角形的外接圆(已知不在同一直线上的三点求经过三点的圆)/*三角形的外接圆pku_1329*/#include#includeconstdoubleeps=1e-6;typedefstructTPoint{doublex;doubley;}TPoint;typedefstructTTriangle{TPointt[3];}TTriangle;typed

8、efstructTCircle{TPointcentre;doubler;}TCircle;doubledistance(TPointp1,TPointp2){//计算平面上两个点之间的距离returnsqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}doubletriangleArea(TTrianglet){//已知三角形三个顶点的坐标,求三角形的面积returnfabs(t.

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。