acm必做50题解题-计算几何

acm必做50题解题-计算几何

ID:20357568

大小:56.50 KB

页数:28页

时间:2018-10-12

acm必做50题解题-计算几何_第1页
acm必做50题解题-计算几何_第2页
acm必做50题解题-计算几何_第3页
acm必做50题解题-计算几何_第4页
acm必做50题解题-计算几何_第5页
资源描述:

《acm必做50题解题-计算几何》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、ACM必做50题的解题-计算几何ACM必做50题的解题-计算几何.txt生活,是用来经营的,而不是用来计较的。感情,是用来维系的,而不是用来考验的。爱人,是用来疼爱的,而不是用来伤害的。金钱,是用来享受的,而不是用来衡量的。谎言,是用来击破的,而不是用来装饰的。信任,是用来沉淀的,而不是用来挑战的。POJ1113WALL计算几何,求凸包这题的结果等于这个多边形构成的凸包的周长加上以所给半径为半径的圆的周长步骤如下:1)算法首先寻找最最靠下方的点,如果遇到y坐标相同,则寻找x坐标最小的点firstP2)然后根据所有点相对于firstP的偏角的大小进行排序,遇到偏角相等的,只

2、取距离firstP最远的点(排序利用自己手写的快排)3)然后利用Graham算法求凸包4)最后直接求职#include#include#definePI3.1415926#defineMAX_N1000usingnamespacestd;//存储原始输入的坐标值,rad是输入的半径doublecord[MAX_N+2][2],rad;intseq[MAX_N+2];intstack[MAX_N+2];intn,top;intfirstP;intrealN;voidswap(intpos1,intpos2){inttemp=seq[pos1

3、];seq[pos1]=seq[pos2];seq[pos2]=temp;}intdir(intnodes,intnode1,intnode2){doublex1=cord[node1][0],y1=cord[node1][1];doublex2=cord[node2][0],y2=cord[node2][1];doublesx=cord[nodes][0],sy=cord[nodes][1];return(x2-sx)*(y1-sy)-(x1-sx)*(y2-sy);}doublegetDist(intnode1,intnode2){doublex1=cord[node

4、1][0],y1=cord[node1][1];doublex2=cord[node2][0],y2=cord[node2][1];doubleres=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));returnres;}intcompare(intnode1,intnode2){doublex1=cord[node1][0],y1=cord[node1][1];doublex2=cord[node2][0],y2=cord[node2][1];doublesx=cord[firstP][0],sy=cord[firstP][1];double

5、type=dir(firstP,node1,node2);if(type==0){doubledist1=(x1-sx)*(x1-sx)+(y1-sy)*(y1-sy);doubledist2=(x2-sx)*(x2-sx)+(y2-sy)*(y2-sy);if(dist1>dist2)return-2;elseif(dist1==dist2)return0;elsereturn2;}elseif(type>0)return1;elsereturn-1;}voidfastSort(intstart,intend){if(start

6、;intposS=start,posE=end+1;while(true){while(compare(seq[++posS],seq[curPos])<0&&posS0&&posE>start);if(posS

7、//最低最左点不参加排序if(i==firstP)continue;seq[++s]=i;}realN=n-1;fastSort(1,realN);//清理夹角相同但是距离不同的点,只取举例firstP最远的点i=1;while(i

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

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

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