浙江大学acm模板.docx

《浙江大学acm模板.docx》由会员分享，可在线阅读，更多相关《浙江大学acm模板.docx（111页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Zhejiang University 浙江大学 ACM 模板1几何.31. 1注意31.4 多边形切割.81.7 球面.151. 10 凸包.261. 13整数函数.302、组合.322. 1组合公式.322.4 置换（polya） 353、数据结构.363. 1并查集.363. 4子段和.434、数论.454. 1阶乘最后非位.454. 4欧拉函数.485、数值计算.485. 1定积分计算（Romberg） 486、图论NP搜索.526. I最大团.527、图论连通性.551.2几何公式.31. 5浮点函数.91.8三角形.161. 11 网格.272.2排列组合生成.332. 5字典序全

2、排列.353. 2 堆.373. 5子阵和.444.2模线性方程组.455.2多项式求根（牛顿法）506. 2 最大团（n64） （faster）1.3多边形.51. 6面积.141.9三维几何.181. 12 圆.292. 3 生成 gray 码.352.6字典序组合.363. 3线段树.394.3 素数.475. 3周期性方程（追赶法）51537. 1无向图关键点（dfs邻接阵）557.3 无向图的块（bfs邻接阵）577.5 有向图强连通分支（dfs/bfs邻接阵）588、图论一匹配.608. 1二分图最大匹配（hungary邻接表）607.2无向图关键边（dfs邻接阵）567.4无向图

3、连通分支（dfs/bfs邻接阵）587.6有向图最小点基（邻接阵）608. 2二分图最大匹配（hungary邻接阵）618. 3二分图最大匹配（hungary正向表）618. 4二分图最佳匹配（kuhnjnunkras邻接阵）628.5 一般图匹配（邻接表）638.6 一般图匹配（邻接阵）648. 7一般图匹配（正向表）659、图论网络流.669. 1最大流（邻接阵）66 9. 2上下界最大流（邻接阵）669. 3上下界最小流（邻接阵）679.4最大流无流量（邻接阵）689.5最小费用最大流（邻接阵）6810、图论应用.6910. 1欧拉回路（邻接阵）6910.4 拓扑排序（邻接阵）7210.

4、7 最小边割集.7511、图论支撑树.7810.8 树的前序表转化.7010. 5最佳边割集.7310. 8最小点割集.7610.3树的优化算法.7110. 6最佳点割集.7410.9最小路径覆盖.7711. !最小生成树（kruskal邻接表）7811.2最小生成树（kruskal正向表）7911. 3最小生成树（prim+binary_heap邻接表）8111. 4最小生成树（prim+binary_heap正向表）8211. 5最小生成树（prim+mapped_heap邻接表）8311. 6最小生成树（prim+mapped_heap正向表）8411.7最小生成树（prim邻接阵）85

5、11.8最小树形图（邻接阵）8612、图论最短路径.8812. 112.212.312.412.512.612.712.812.9最短路径（单源bellman_ford邻接阵）88最短路径（単源di jkstra+bfs邻接表）88最短路径（单源di jkstra+bfs正向表）89最短路径（单源di jkstra+binary_heap邻接表）89 最短路径（单源di jkstra+binary_heap正向表）90 最短路径（单源di jkstra+mapped heap邻接表）91 最短路径（单源di jkstra+mapped_heap正向表）93 最短路径（単源di jkstra邻接

6、阵）94最短路径（多源floyd_warshall邻接阵）9413.3布尔母函数.9613. 6模式匹配（kmp） 9913. 9最长公共单调子序列.10013. 12最大子段和.10314. 3 矩阵.11214.6 日期.11613、应用.9513. 1 Joseph 问题.9513 . 4 第 k 元素.9714 .7逆序对数.9913. 10最长子序列.10113、 13最大子阵和.10314、 其它.10414. 1大数（只能处理正数）14.4线性方程组.11413.2 N皇后构造解.9613.5 幻方构造.9713.8 字符串最小表示.9913. 11最大子串匹配.10210414

7、.2 分数.11014.5线性相关.1151、几何1.1注意1 .注意舍入方式(0.5的舍入方向);防止输出.2 .几何题注意多测试不对称数据.3 .整数几何注意xmult和dmult是否会出界;符点几何注意eps的使用.4 .避免使用斜率;注意除数是否会为0.5 .公式一定要化简后再代入.6 .判断同一个2*PI域内两角度差应该是 abs(al-a2)pi+pi-beta;相等应该是abs(al-a2)pi+pi-eps;7 .需要的话尽量使用atan2,注意;atan2(0, 0)=0, atan2(l, 0) =pi/2, atan2 (-1, 0) =-pi/2, atan2(0, 1

8、)=0, atan2(0, -l)=pi.8 . cross product = |u|*|v|*sin(a) dot product = |u|*|v|*cos(a)9 . (Pl-P0)x(P2-P0)结果的意义;正:P0, Pl在PO, P2顺时针(0, pi)内负:P0, Pl在P0, P2逆时针(0,pi)内0 : , 共线,夹角为 或 pi10 .误差限缺省使用le-8!1. 2几何公式三角形:1 .半周长 P=(a+b+c)/22.面积 S=aHa/2=absin(C)/2=sqrt(P(P-a) (P-b) (P-c)3.中线 Ma=sqrt (2 (b 2+c2)-a2)/2

9、=sqrt (b2+c2+2bccos (A) )/24 .角平分线 Ta=sqrt(bc(b+c) 2-a2)/(b+c)=2bccos(A/2)/(b+c)5 .高线 Ha=bs i n (C) =cs i n (B) =sqrt (b 2- (a* 2+b 2-c 2) / (2a) ) 2)6 .内切圆半径 r=S/P=asin(B/2)sin(C/2)/sin(B+C)/2) =4Rsin(A/2)sin(B/2)sin(C/2)=sqrt(P-a)(P-b)(P-c)/P) =Ptan(A/2)tan(B/2)tan(C/2)7 .外接圆半径 R=abc/(4S)=a/(2sin(

10、A)=b/(2sin(B)=c/(2sin(C)四边形:DI, D2为对角线,M对角线中点连线,A为对角线夹角1. a2+b*2+c 2+d2=012+D22+4M22. S=DlD2sin(A)/2(以下对圆的内接四边形)3. ac+bd=DlD24. S=sqrt (P-a) (P-b) (P-c) (P-d), P 为半周长正n边形:R为外接圆半径,r为内切圆半径1 .中心角A=2PI/n2 .内角 C=(n-2)PI/n3 .边长 a=2sqrt (R2-r-2)=2Rsin(A/2)=2rtan(A/2)4 .面积 S=nar/2=nr2tan(A/2) =nR 2sin(A)/2=

11、na2/(4tan(A/2)圆:1 .弧长l=rA2 .弦长 a=2sqrt (2hr-h 2) =2rsin (A/2)3 .弓形高 h=r-sqrt(r-2-a2/4)=r(1-cos(A/2) =atan(A/4)/24 .扇形面积 Sl=rl/2=r2A/25 .弓形面积 S2= (rl-a(r-h)/2=r*2(A-sin(A)/2棱柱:1 .体积V=Ah,A为底面积,h为高2 .侧面积S=lp, 1为极长,p为直截面周长3 .全面积T=S+2A棱锥:1 .体积V=Ah/3,A为底面积,h为高(以下对正棱锥)2 .侧面积S=lp/2,1为斜高,p为底面周长3 .全面积T=S+A棱台:

12、1 .体积 V=(Al+A2+sqrt(AlA2)h/3,Al.A2 为上下底面积,h 为高 (以下为正棱台)2 .侧面积S=(pl+p2)l/2,pl.p2为上下底面周长,1为斜高3 .全面积 T=S+A1+A2圆柱：1 .侧面积S=2PIrh2 .全面积 T=2PIr(h+r)3 .体积 V=PIr2h圆锥：1 .母线 !=sqrt (h 2+r*2)2 .侧面积S=PIrl3 .全面积 T=PIr(l+r)4 .体积 V=PIr2h/3圆台:1 .母线 !=sqrt (h2+(rl-r2) 2)2 .侧面积 S=PI(rl+r2)l3 .全面积 T=PIrl(l+rl)+PIr2(l+r

13、2)4 .体积 V=PI(rr2+r2A2+rlr2)h/3球:1 .全面积 T=4PIr-22 .体积 V=4PIr3/3球台:1 .侧面积S=2PIrh2 .全面积 T=PI(2rh+rr2+r2 2)3 .体积 V=PIh(3(rr2+r22)+2)/6球扇形:1 .全面积T=PIr(2h+rO),h为球冠髙,rO为球冠底面半径2 .体积 V=2PI/2h/33 .3多边形include #include #define MAXN 1000#define offset 10000# define eps le-8# define zero(x) (x)0?(x):-(x)eps?l: (

14、x)-eps?2:0)struct point double x,y;struct line (point a,b;/double xmult(point pl,point p2, point pO)return (pl. x-p0. x)*(p2. y-pO. y)- (p2. x-p0. x)*(pl. y-pO. y); 判定凸多边形,顶点按顺时针或逆时针给出,允许相邻边共线 int is_convex(int n, point* p)int i, s3 = l, 1,1;for (i=0;in&sl|s2;i+)s_sign(xmult(p(i+l)%n, p(i+2)%n, pi)=

15、0;return s 1|s2;判定凸多边形,顶点按顺时针或逆时针给出,不允许相邻边共线 int is_convex_v2(int n, point* p)int i, s3 = l, 1, 1;for (i=0;in&s0&sl|s2;i+)s_sign(xmult(p(i+l)%n, p(i+2)%n, pi)=0; return s0&sl|s2;判点在凸多边形内或多边形边匕顶点按顺时针或逆时针给出int inside_convex(point q, int n,point* p)int i, s3 = l, 1, 1;for (i=0; in&sl I s；i+)s _sign (xm

16、ult (p (i+l)%n, q, pi)=0;return s 1|s2;判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回 int inside_convex v2 (point q,int n, point* p)int i, s3 = l, 1,1;for (i=0;in&s0&sl|s2;i+)s_sign(xmult(p(i+l)%n, q, pi)=0;return s0&sl|s2;判点在任意多边形内,顶点按顺时针或逆时针给出/on.edge表示点在多边形边上时的返回值,offset为多边形坐标上限int inside_po1ygon(point q, int n,

17、 point* p, int on_edge=l)point q2;int i=0,count;while (in)for (count二i=0, q2. x=rand()+offset, q2. y=rand()+offset; in; i+)if(zero(xmult (q, pi, p(i+l)%n)&(pi. x-q. x)*(p(i+l)%n. x-q. x)eps&(pi. y-q. y)*(p(i+l)%n. y-q. y)eps)return on_edge;else if (zero(xmu11 (q, q2, pi)break;elseif (xmult (q, pi, q

18、2)*xmult (q, p(i+l)%n, q2)-eps&xmult (pi, q, p(i+l)%n)*xmult ( pi, q2, p(i+l)%n)-eps)count+;return count&l;inline int opposite_side(point pl,point p2, point 11,point 12) return xmult(11, pl, 12)*xmult(11, p2,12)-eps;inline int dot_online_in(point p,point 11, point 12)returnzero(xmult(p, 11,12)&(11.

19、x-p. x)*(12. x-p. x)epsft&(ll. y-p. y)*(12. y-p. y)eps;判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回1int inside_polygon(point 11, point 12,int n,point* p)point tMAXN, tt;int i, j, k=0;if (!inside_polygon(11, n, p)|!inside_polygon(12, n, p)return 0;for (i=0;in;i+)if(opposite_side(11, 12, pi, p(i+l)%n)&opposite_sid

20、e(pi, p(i+l)%n, 11, 12) return 0;else if (dot online in(11,pi, p(i+l)%n)tk+=ll;else if (dot online in(12, pi, p(i+l)%n)tk+=12;else if (dot_online_in(pi, 11,12)tk+=pi;for (i=0;ik;i+)for (j=i+l;jk;j+)tt. x=(t i. x+tj. x)/2;tt. y=(ti. y+tj. y)/2;if (!inside_polygon(tt, n, p)return 0;return 1;point inte

21、rsection(line u,line v)point ret=u. a;double t= (u. a. x-v. a. x) * (v. a. y-v. b. y) - (u. a. y-v. a. y) * (v, a. x-v. b. x)/ (u. a. x-u. b. x) * (v. a. y-v. b. y) - (u. a. y-u. b. y) * (v. a. x-v. b. x);ret. x+= (u. b. x-u. a. x) *t;ret. y+=(u. b. y-u. a. y) *t;return ret;point barycenter(point a,

22、 point b,point c) line u, v;u. a. x= (a. x+b. x)/2;u. a. y= (a. y+b. y) /2;u. b=c;v. a. x= (a. x+c. x) /2;v. a. y= (a. y+c. y)/2;v.b=b;return intersection(u, v);多边形重心point barycenter(int n, point* p)point ret, t;double tl=0, t2;int i;ret. x=ret. y=0;for (i=l;ieps) t二barycenter(p, pi, pi+l)； ret. x+=

23、t. x*t2;ret. y+=t. y*t2; tl+=t2;if (fabs(tl)eps)ret.x/=tl, ret. y/=tl; return ret;1.4多边形切割多边形切割可用于半平面交#define MAXN 100#define eps le-8#define zero(x) (x)0?(x):-(x)eps;point intersection(point ul,point u2,point vl,point v2) point ret=ul;double t=(ul. x-vl. x)*(vl. y-v2. y)-(ul. y-vl. y)*(vl. x-v2. x)

24、/(ul. x-u2. x)*(vl. y-v2. y)-(ul. y-u2. y)*(vl. x-v2. x);ret. x+= (u2. x-u 1. x)*t;ret. y+=(u2. y-ul. y)*t;return ret;将多边形沿11, 12确定的直线切割在side侧切割,保证11,12, side不共线void polygon_cut(int& n, point* p,point 11, point 12,point side)point pp100;int m=0, i;for (i=0;in;i+)if (same side(pi, side, 11, 12) ppm+=

25、pi;if(!same_side(pi, p(i+l)%n, 11,12)&!(zero(xmult(pi, 11, 12)&zero(xmult(p(i+l )%n,ll,12)ppm+=intersection(pi, p(i+l)%n, 11, 12);for (n二i二;im;i+)if (! i I I !zero(ppi. x-ppi-l. x) | | !zero(ppi. y-ppiT y) pn+=ppi;if (zero(px-p. x)&zero(pn-l. y-p0.y)n;if (n3)n=0;1.5 浮点函数浮点几何函数库#include #define eps l

26、e-8#define zero(x) (x)0?(x):-(x)eps)struct pointdouble x,y;struct line point a, b;计算 cross product (Pl-P0)x(P2-P0)double xmult(point pl,point p2, point pO)return (pl. x-pO. x)*(p2. y-pO. y)-(p2. x-pO. x)*(pl. y-pO. y);/double xmult(double xl, double yl, double x2, double y2, double xO, double yO) re

27、turn (xl-x0)* (y2-y0)-(x2-x0)*(y1-yO);计算 dot product (P1-P0). (P2-P0)double dmult(point pl,point p2, point pO)return (pl. x-pO. x) *(p2. x-pO. x) + (pl. y-pO. y)*(p2. y-pO. y);/double dmult(double xl,double yl,double x2, double y2,double xO, double yO) return (xl-xO)*(x2-x0)+(yl-yO)*(y2-yO);两点距离doub

28、le distance(point pl, point p2)return sqrt(pl. x-p2. x)*(pl. x-p2. x) + (pl. y-p2. y)*(pl. y-p2. y);double distance(double xl, double yl, double x2, double y2) return sqrt(xl-x2)*(xl-x2) + (yl-y2)*(yl-y2);/判三点共线int dots_ inline(point pl, point p2, point p3) return zero(xmult(pl, p2, p3);int dots_inl

29、ine(double xl, double yl,double x2,double y2,double x3, double y3) return zero(xmult(xl, yl, x2, y2, x3, y3);判点是否在线段匕包括端点int dot_online_in(point p,line 1)returnzero(xmult (p, 1. a, 1. b)&(1. a. x-p. x)*(l. b. x-p. x)eps&(l. a. y-p. y)*(1. b. y-p. y)epsint dot_online_in(point p,point 11, point 12) re

30、turnzero(xmult (p, 11, 12)&(11. x-p. x)*(12. x-p. x)eps&(ll. y-p. y)*(12. y-p. y)eps;int dot online_in(double x, double y, double xl,double yl,double x2, double y2) returnzero(xmult (x, y, xl, yl, x2, y2)&(xl-x)*(x2-x) eps&(yl-y)*(y2-y)eps;int same_side(point pl,point p2,point 11,point 12) return xm

31、ult(11, pl, 12)*xmult(11, p2, 12)eps;判两点在线段异侧,点在线段上返回int opposite_side(point pl,point p2,line 1) return xmult (1. a, pl, 1. b)*xmult (1. a, p2,1. b)一eps;int opposite_side(point pl, point p2, point 11,point 12) return xmult(11, pl, 12)*xmult(11, p2, 12)eps)return distance(p, 1. a)eps)return distance(p, ll)eps