ACM必做50题的解题-计算几何.doc

《ACM必做50题的解题-计算几何.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、POJ1113WALL计算几何，求凸包这题的结果等于这个多边形构成的凸包的周长加上以所给半径为半径的圆的周长步骤如下：1)算法首先寻找最最靠下方的点，如果遇到y坐标相同，则寻找x坐标最小的点firstP2)然后根据所有点相对于firstP的偏角的大小进行排序，遇到偏角相等的，只取距离firstP最远的点(排序利用自己手写的快排)3)然后利用Graham算法求凸包4)最后直接求职#include#include#definePI3.#defineMAX_N1000usingnames

2、pacestd;//存储原始输入的坐标值，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];seq[pos1]=seq[pos2];seq[pos2]=temp;}intdir(intnodes,intnode1,intnode2){doublex1=cord[node1][0],y1

3、=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[node1][0],y1=cord[node1][1];doublex2=cord[node2][0],y2=cord[node2][1];doub

4、leres=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];doubletype=dir(firstP,node1,node2);if(type==0){

5、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、rt,posE=end+1;while(true){while(compare(seq[++posS],seq[curPos])<0&&posS0&&posE>start);if(posS

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

8、ndQ(){intnodes,node1,node2,type;top=0;stack[top++]=firstP;ints=1;intc=0;while(c<2){if(seq[s]!=-1){c++;stack[top++]=seq[s];}s++;}for(;s<=realN;s++){if(seq[s]==-1)continue;while(true