加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 清华大学ACM模板

清华大学ACM模板.pdf

清华大学ACM模板

工大路杰出青年
2011-12-29 0人阅读 举报 0 0 暂无简介

简介:本文档为《清华大学ACM模板pdf》,可适用于IT/计算机领域

清华大学代码册、几何注意几何公式多边形多边形切割浮点函数面积球面三角形三维几何凸包网格圆整数函数、组合组合公式排列组合生成生成gray码置换(polya)字典序全排列字典序组合、结构并查集堆线段树子段和子阵和、数论阶乘最后非位模线性方程组素数欧拉函数、数值计算定积分计算(Romberg)多项式求根(牛顿法)周期性方程(追赶法)、图论NP搜索最大团最大团(n<)(faster)、图论连通性无向图关键点(dfs邻接阵)无向图关键边(dfs邻接阵)无向图的块(bfs邻接阵)无向图连通分支(dfsbfs邻接阵)有向图强连通分支(dfsbfs邻接阵)有向图最小点基(邻接阵)、图论匹配二分图最大匹配(hungary邻接表)二分图最大匹配(hungary邻接阵)二分图最大匹配(hungary正向表)二分图最佳匹配(kuhnmunkras邻接阵)一般图匹配(邻接表)一般图匹配(邻接阵)一般图匹配(正向表)、图论网络流最大流(邻接阵)上下界最大流(邻接阵)上下界最小流(邻接阵)最大流无流量(邻接阵)最小费用最大流(邻接阵)、图论应用欧拉回路(邻接阵)树的前序表转化树的优化算法拓扑排序(邻接阵)最佳边割集最佳点割集最小边割集最小点割集最小路径覆盖、图论支撑树最小生成树(kruskal邻接表)最小生成树(kruskal正向表)最小生成树(primbinaryheap邻接表)最小生成树(primbinaryheap正向表)最小生成树(primmappedheap邻接表)最小生成树(primmappedheap正向表)最小生成树(prim邻接阵)最小树形图(邻接阵)、图论最短路径最短路径(单源bellmanford邻接阵)最短路径(单源dijkstrabfs邻接表)最短路径(单源dijkstrabfs正向表)最短路径(单源dijkstrabinaryheap邻接表)最短路径(单源dijkstrabinaryheap正向表)最短路径(单源dijkstramappedheap邻接表)最短路径(单源dijkstramappedheap正向表)最短路径(单源dijkstra邻接阵)最短路径(多源floydwarshall邻接阵)、应用Joseph问题N皇后构造解布尔母函数第k元素幻方构造模式匹配(kmp)逆序对数字符串最小表示最长公共单调子序列最长子序列最大子串匹配最大子段和最大子阵和、其它大数(只能处理正数)分数矩阵线性方程组线性相关日期、几何注意注意舍入方式(的舍入方向)防止输出几何题注意多测试不对称数据整数几何注意xmult和dmult是否会出界符点几何注意eps的使用避免使用斜率注意除数是否会为公式一定要化简后再代入判断同一个*PI域内两角度差应该是abs(aa)<beta||abs(aa)>pipibeta相等应该是abs(aa)<eps||abs(aa)>pipieps需要的话尽量使用atan,注意:atan(,)=,atan(,)=pi,atan(,)=pi,atan(,)=,atan(,)=picrossproduct=|u|*|v|*sin(a)dotproduct=|u|*|v|*cos(a)(PP)x(PP)结果的意义:正:<P,P>在<P,P>顺时针(,pi)内负:<P,P>在<P,P>逆时针(,pi)内:<P,P>,<P,P>共线,夹角为或pi误差限缺省使用e!几何公式三角形:半周长P=(abc)面积S=aHa=absin(C)=sqrt(P(Pa)(Pb)(Pc))中线Ma=sqrt((b^c^)a^)=sqrt(b^c^bccos(A))角平分线Ta=sqrt(bc((bc)^a^))(bc)=bccos(A)(bc)高线Ha=bsin(C)=csin(B)=sqrt(b^((a^b^c^)(a))^)内切圆半径r=SP=asin(B)sin(C)sin((BC))=Rsin(A)sin(B)sin(C)=sqrt((Pa)(Pb)(Pc)P)=Ptan(A)tan(B)tan(C)外接圆半径R=abc(S)=a(sin(A))=b(sin(B))=c(sin(C))四边形:D,D为对角线,M对角线中点连线,A为对角线夹角a^b^c^d^=D^D^M^S=DDsin(A)(以下对圆的内接四边形)acbd=DDS=sqrt((Pa)(Pb)(Pc)(Pd)),P为半周长正n边形:R为外接圆半径,r为内切圆半径中心角A=PIn内角C=(n)PIn边长a=sqrt(R^r^)=Rsin(A)=rtan(A)面积S=nar=nr^tan(A)=nR^sin(A)=na^(tan(A))圆:弧长l=rA弦长a=sqrt(hrh^)=rsin(A)弓形高h=rsqrt(r^a^)=r(cos(A))=atan(A)扇形面积S=rl=r^A弓形面积S=(rla(rh))=r^(Asin(A))棱柱:体积V=Ah,A为底面积,h为高侧面积S=lp,l为棱长,p为直截面周长全面积T=SA棱锥:体积V=Ah,A为底面积,h为高(以下对正棱锥)侧面积S=lp,l为斜高,p为底面周长全面积T=SA棱台:体积V=(AAsqrt(AA))h,AA为上下底面积,h为高(以下为正棱台)侧面积S=(pp)l,pp为上下底面周长,l为斜高全面积T=SAA圆柱:侧面积S=PIrh全面积T=PIr(hr)体积V=PIr^h圆锥:母线l=sqrt(h^r^)侧面积S=PIrl全面积T=PIr(lr)体积V=PIr^h圆台:母线l=sqrt(h^(rr)^)侧面积S=PI(rr)l全面积T=PIr(lr)PIr(lr)体积V=PI(r^r^rr)h球:全面积T=PIr^体积V=PIr^球台:侧面积S=PIrh全面积T=PI(rhr^r^)体积V=PIh((r^r^)h^)球扇形:全面积T=PIr(hr),h为球冠高,r为球冠底面半径体积V=PIr^h多边形#include<stdlibh>#include<mathh>#defineMAXN#defineoffset#defineepse#definezero(x)(((x)>(x):(x))<eps)#definesign(x)((x)>eps:((x)<eps:))structpoint{doublex,y}structline{pointa,b}doublexmult(pointp,pointp,pointp){return(pxpx)*(pypy)(pxpx)*(pypy)}判定凸多边形,顶点按顺时针或逆时针给出,允许相邻边共线intisconvex(intn,point*p){inti,s={,,}for(i=i<ns|si)ssign(xmult(p(i)n,p(i)n,pi))=returns|s}判定凸多边形,顶点按顺时针或逆时针给出,不允许相邻边共线intisconvexv(intn,point*p){inti,s={,,}for(i=i<nss|si)ssign(xmult(p(i)n,p(i)n,pi))=returnss|s}判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出intinsideconvex(pointq,intn,point*p){inti,s={,,}for(i=i<ns|si)ssign(xmult(p(i)n,q,pi))=returns|s}判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回intinsideconvexv(pointq,intn,point*p){inti,s={,,}for(i=i<nss|si)ssign(xmult(p(i)n,q,pi))=returnss|s}判点在任意多边形内,顶点按顺时针或逆时针给出onedge表示点在多边形边上时的返回值,offset为多边形坐标上限intinsidepolygon(pointq,intn,point*p,intonedge=){pointqinti=,countwhile(i<n)for(count=i=,qx=rand()offset,qy=rand()offseti<ni)if(zero(xmult(q,pi,p(i)n))(pixqx)*(p(i)nxqx)<eps(piyqy)*(p(i)nyqy)<eps)returnonedgeelseif(zero(xmult(q,q,pi)))breakelseif(xmult(q,pi,q)*xmult(q,p(i)n,q)<epsxmult(pi,q,p(i)n)*xmult(pi,q,p(i)n)<eps)countreturncount}inlineintoppositeside(pointp,pointp,pointl,pointl){returnxmult(l,p,l)*xmult(l,p,l)<eps}inlineintdotonlinein(pointp,pointl,pointl){returnzero(xmult(p,l,l))(lxpx)*(lxpx)<eps(lypy)*(lypy)<eps}判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回intinsidepolygon(pointl,pointl,intn,point*p){pointtMAXN,ttinti,j,k=if(!insidepolygon(l,n,p)||!insidepolygon(l,n,p))returnfor(i=i<ni)if(oppositeside(l,l,pi,p(i)n)oppositeside(pi,p(i)n,l,l))returnelseif(dotonlinein(l,pi,p(i)n))tk=lelseif(dotonlinein(l,pi,p(i)n))tk=lelseif(dotonlinein(pi,l,l))tk=pifor(i=i<ki)for(j=ij<kj){ttx=(tixtjx)tty=(tiytjy)if(!insidepolygon(tt,n,p))return}return}pointintersection(lineu,linev){pointret=uadoublet=((uaxvax)*(vayvby)(uayvay)*(vaxvbx))((uaxubx)*(vayvby)(uayuby)*(vaxvbx))retx=(ubxuax)*trety=(ubyuay)*treturnret}pointbarycenter(pointa,pointb,pointc){lineu,vuax=(axbx)uay=(ayby)ub=cvax=(axcx)vay=(aycy)vb=breturnintersection(u,v)}多边形重心pointbarycenter(intn,point*p){pointret,tdoublet=,tintiretx=rety=for(i=i<ni)if(fabs(t=xmult(p,pi,pi))>eps){t=barycenter(p,pi,pi)retx=tx*trety=ty*tt=t}if(fabs(t)>eps)retx=t,rety=treturnret}多边形切割多边形切割可用于半平面交#defineMAXN#defineepse#definezero(x)(((x)>(x):(x))<eps)structpoint{doublex,y}doublexmult(pointp,pointp,pointp){return(pxpx)*(pypy)(pxpx)*(pypy)}intsameside(pointp,pointp,pointl,pointl){returnxmult(l,p,l)*xmult(l,p,l)>eps}pointintersection(pointu,pointu,pointv,pointv){pointret=udoublet=((uxvx)*(vyvy)(uyvy)*(vxvx))((uxux)*(vyvy)(uyuy)*(vxvx))retx=(uxux)*trety=(uyuy)*treturnret}将多边形沿l,l确定的直线切割在side侧切割,保证l,l,side不共线voidpolygoncut(intn,point*p,pointl,pointl,pointside){pointppintm=,ifor(i=i<ni){if(sameside(pi,side,l,l))ppm=piif(!sameside(pi,p(i)n,l,l)!(zero(xmult(pi,l,l))zero(xmult(p(i)n,l,l))))ppm=intersection(pi,p(i)n,l,l)}for(n=i=i<mi)if(!i||!zero(ppixppix)||!zero(ppiyppiy))pn=ppiif(zero(pnxpx)zero(pnypy))nif(n<)n=}浮点函数浮点几何函数库#include<mathh>#defineepse#definezero(x)(((x)>(x):(x))<eps)structpoint{doublex,y}structline{pointa,b}计算crossproduct(PP)x(PP)doublexmult(pointp,pointp,pointp){return(pxpx)*(pypy)(pxpx)*(pypy)}doublexmult(doublex,doubley,doublex,doubley,doublex,doubley){return(xx)*(yy)(xx)*(yy)}计算dotproduct(PP)(PP)doubledmult(pointp,pointp,pointp){return(pxpx)*(pxpx)(pypy)*(pypy)}doubledmult(doublex,doubley,doublex,doubley,doublex,doubley){return(xx)*(xx)(yy)*(yy)}两点距离doubledistance(pointp,pointp){returnsqrt((pxpx)*(pxpx)(pypy)*(pypy))}doubledistance(doublex,doubley,doublex,doubley){returnsqrt((xx)*(xx)(yy)*(yy))}判三点共线intdotsinline(pointp,pointp,pointp){returnzero(xmult(p,p,p))}intdotsinline(doublex,doubley,doublex,doubley,doublex,doubley){returnzero(xmult(x,y,x,y,x,y))}判点是否在线段上,包括端点intdotonlinein(pointp,linel){returnzero(xmult(p,la,lb))(laxpx)*(lbxpx)<eps(laypy)*(lbypy)<eps}intdotonlinein(pointp,pointl,pointl){returnzero(xmult(p,l,l))(lxpx)*(lxpx)<eps(lypy)*(lypy)<eps}intdotonlinein(doublex,doubley,doublex,doubley,doublex,doubley){returnzero(xmult(x,y,x,y,x,y))(xx)*(xx)<eps(yy)*(yy)<eps}判点是否在线段上,不包括端点intdotonlineex(pointp,linel){returndotonlinein(p,l)(!zero(pxlax)||!zero(pylay))(!zero(pxlbx)||!zero(pylby))}intdotonlineex(pointp,pointl,pointl){returnd

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/28

清华大学ACM模板

仅供在线阅读

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利