ACM_計(jì)算幾何_源碼

《ACM_計(jì)算幾何_源碼》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、------------------------------------------------------------------------------------------------------------------------------------------(1)凸包/*凸包c(diǎn)ug_1038*/#include#includestructpoint{intx,y;}pp;pointp[100005];intstack[100005],top;intdis(

2、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.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

3、;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(pointp[],intn,intstack[],int&top){inti,u;u=0;65for(i=1;i

4、(p,0,u);pp=p[0];qsort(p+1,n-1,sizeof(p[0]),cmp);stack[0]=0;stack[1]=1;top=1;for(i=2;i=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++){scan

5、f("%d",&n);for(j=0;j

6、---------------------------------------------------------------------(2)判斷兩條線段是否相交(平行，不平行)boolisIntersected(TPoints1,TPointe1,TPoints2,TPointe2){//判斷線段是否相交//1.快速排斥試驗(yàn)判斷以兩條線段為對(duì)角線的兩個(gè)矩形是否相交65//2.跨立試驗(yàn)if((max(s1.x,e1.x)>=min(s2.x,e2.x))&&(max(s2.x,e2.x)>=min(s1.x,

7、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)&&(multi(s1,e2,s2)*multi(e2,e1,s2)>=0))returntrue;returnfalse;}(3)三角形的外接圓(已知不在同一直線上的三點(diǎn)求經(jīng)過(guò)三點(diǎn)的圓)/*三角形的外接圓pku_1329*/#include#include

8、constdoubleeps=1e-6;typedefstructTPoint{doublex;doubley;}TPoint;typedefstructTTriangle{TPointt[3];}TTriangle;typedefstructTCircle{TPointcentre;doubler;}TCircle;doubledistance(TPointp1,TPointp2){