acm 算法模板 适合初学者使用

1三角形面积计算...............................................................................................................1字典树模板.......................................................................................................................2求线段所在直线...............................................................................................................5求外接圆...........................................................................................................................5求内接圆...........................................................................................................................6判断点是否在直线上.......................................................................................................8简单多边形面积计算公式...............................................................................................8stein算法求最大共约数..................................................................................................9最长递增子序列模板——o(nlogn算法实现)................................................................9判断图中同一直线的点的最大数量.............................................................................10公因数和公倍数.............................................................................................................12已知先序中序求后序.....................................................................................................12深度优先搜索模板.........................................................................................................13匈牙利算法——二部图匹配BFS实现........................................................................15带输出路径的prime算法.............................................................................................17prime模板......................................................................................................................18kruskal模板....................................................................................................................19dijsktra.............................................................................................................................22并查集模板.....................................................................................................................23高精度模板.....................................................................................................................24三角形面积计算//已知三条边和外接圆半径，公式为s=a*b*c/(4*R)doubleGetArea(doublea,doubleb,doublec,doubleR){returna*b*c/4/R;}//已知三条边和内接圆半径，公式为s=prdoubleGetArea(doublea,doubleb,doublec,doubler){returnr*(a+b+c)/2;}//已知三角形三条边，求面积doubleGetArea(doulea,doubleb,doublec){doublep=(a+b+c)/2;returnsqrt(p*(p-a)*(p-b)*(p-c));}2//已知道三角形三个顶点的坐标structPoint{doublex,y;Point(doublea=0,doubleb=0){x=a;y=b;}};doubleGetArea(Pointp1,Pointp2,Pointp3){doublet=-p2.x*p1.y+p3.x*p1.y+p1.x*p2.y-p3.x*p2.y-p1.x*p3.y+p2.x*p3.y;if(t0)t=-t;returnt/2;}字典树模板#includestdio.h#includestring.h#includememory.h#defineBASE_LETTER'a'#defineMAX_TREE35000#defineMAX_BRANCH26struct{intnext[MAX_BRANCH];//记录分支的位置intc[MAX_BRANCH];//查看分支的个数intflag;//是否存在以该结点为终止结点的东东，可以更改为任意的属性}trie[MAX_TREE];intnow;voidinit(){now=0;memset(&trie[now],0,sizeof(trie[now]));3now++;}intadd(){memset(&trie[now],0,sizeof(trie[now]));returnnow++;}intinsert(char*str){intpre=0,addr;while(*str!=0){addr=*str-BASE_LETTER;if(!trie[pre].next[addr])trie[pre].next[addr]=add();trie[pre].c[addr]++;pre=trie[pre].next[addr];str++;}trie[pre].flag=1;returnpre;}intsearch(char*str){intpre=0,addr;while(*str!=0){addr=*str-BASE_LETTER;if(!trie[pre].next[addr])return0;pre=trie[pre].next[addr];str++;}if(!trie[pre].flag)return0;4returnpre;}pku2001题，源代码：voidcheck(char*str){intpre=0,addr;while(*str!=0){addr=*str-BASE_LETTER;if(trie[pre].c[addr]==1){printf(%c\n,*str);return;}printf(%c,*str);pre=trie[pre].next[addr];str++;}printf(\n);}charinput[1001][25];intmain(){inti=0,j;init();while(scanf(%s,input[i])!=EOF){getchar();insert(input[i]);i++;}for(j=0;ji;j++){printf(%s,input[j]);check(input[j]);}return0;}5求线段所在直线//*****************************线段所在的直线structLine{doublea,b,c;};structPoint{doublex,y;}LineGetLine(Pointp1,Pointp2){//ax+by+c=0返回直线的参数Lineline;line.a=p2.y-p1.y;line.b=p1.x-p2.x;line.c=p2.x*p1.y-p1.x*p2.y;returnline;}求外接圆//***************已知三角形三个顶点坐标，求外接圆的半径和坐标********************structPoint{doublex,y;Point(doublea=0,doubleb=0){x=a;y=b;}};structTCircle{doubler;Pointp;}doubledistance(Pointp1,Pointp2){returnsqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}6doubleGetArea(doulea,doubleb,doublec){doublep=(a+b+c)/2;returnsqrt(p*(p-a)*(p-b)*(p-c));}TCircleGetTCircle(Pointp1,Pointp2,Pointp3){doublea,b,c;doublexa,ya,xb,yb,xc,yc,c1,c2;TCircletc;a=distance(p1,p2);b=distance(p2,p3);c=distance(p3,p1);//求半径tc.r=a*b*c/4/GetArea(a,b,c);//求坐标xa=p1.x;ya=p1.b;xb=p2.x;yb=p2.b;xc=p3.x;yc=p3.b;c1=(xa*xa+ya*ya-xb*xb-yb*yb)/2;c2=(xa*xa+ya*ya-xc*xc-yc*yc)/2;tc.p.x=(c1*(ya-yc)-c2*(ya-yb))/((xa-xb)*(ya-yc)-(xa-xc)*(ya-yb));tc.p.y=(c1*(xa-xc)-c2*(xa-xb))/((ya-yb)*(xa-xc)-(ya-yc)*(xa-xb));returntc;}求内接圆structPoint{doublex,y;Point(doublea=0,doubleb=0){x=a;y=b;}};structTCircle{7doubler;Pointp;}do