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

《acm 算法模板 适合初学者使用.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、三角形面积计算1字典树模板2求线段所在直线5求外接圆5求内接圆6判断点是否在直线上8简单多边形面积计算公式8stein算法求最大共约数9最长递增子序列模板——o(nlogn算法实现)9判断图中同一直线的点的最大数量10公因数和公倍数12已知先序中序求后序12深度优先搜索模板13匈牙利算法——二部图匹配BFS实现15带输出路径的prime算法17prime模板18kruskal模板19dijsktra22并查集模板23高精度模板24三角形面积计算//已知三条边和外接圆半径，公式为s=a*b*c/(4*R)doubleGetArea(doublea,doubleb,

2、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));}//已知道三角形三个顶点的坐标structPoint{doublex,y;Point(doublea=0,doubleb

3、=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(t<0)t=-t;returnt/2;}字典树模板#include#include#include#defineBASE_LETTER'a'#defineMAX_TREE35000#defineMAX_BRANCH26struct{   intnext[

4、MAX_BRANCH];//记录分支的位置   intc[MAX_BRANCH];//查看分支的个数   intflag;//是否存在以该结点为终止结点的东东，可以更改为任意的属性}trie[MAX_TREE];intnow;voidinit(){now=0;memset(&trie[now],0,sizeof(trie[now]));   now++;}intadd(){   memset(&trie[now],0,sizeof(trie[now]));   returnnow++;}intinsert(char*str){   intpre=0,addr; 

5、  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

6、)   {       addr=*str-BASE_LETTER;       if(!trie[pre].next[addr])           return0;       pre=trie[pre].next[addr];       str++;   }   if(!trie[pre].flag)       return0;   returnpre;}pku2001题，源代码：voidcheck(char*str){intpre=0,addr;while(*str!=0){  addr=*str-BASE_LETTER;       if(tri

7、e[pre].c[addr]==1)  {   printf("%c",*str);   return;  }    printf("%c",*str);       pre=trie[pre].next[addr];       str++;}printf("");}charinput[1001][25];intmain(){inti=0,j;init();while(scanf("%s",input[i])!=EOF){  getchar();  insert(input[i]);  i++;}for(j=0;j

8、s",input[j])