浙江大学acm模板.docx

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字典序全排列.353. 2 堆.373. 5子阵和.444.2模线性方程组.455.2多项式求根（牛顿法）506. 2 最大团（n<64） （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无向图连通分支（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.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邻接阵）8511.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邻接阵）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.2 分数.11014.5线性相关.1151、几何1.1注意1 .注意舍入方式(0.5的舍入方向);防止输出.2 .几何题注意多测试不对称数据.3 .整数几何注意xmult和dmult是否会出界;符点几何注意eps的使用.4 .避免使用斜率;注意除数是否会为0.5 .公式一定要化简后再代入.6 .判断同一个2*PI域内两角度差应该是 abs(al-a2)<beta|abs(al-a2) >pi+pi-beta;相等应该是abs(al-a2)<eps1|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)=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 : <P0, Pl>, <P0, P2>共线,夹角为 或 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+c"2)-a'2)/2=sqrt (b"2+c"2+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(A)=b/(2sin(B)=c/(2sin(C)四边形:DI, D2为对角线,M对角线中点连线,A为对角线夹角1. a"2+b*2+c " 2+d"2=01"2+D2"2+4M"22. 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=nr"2tan(A/2) =nR 2sin(A)/2=na"2/(4tan(A/2)圆:1 .弧长l=rA2 .弦长 a=2sqrt (2hr-h 2) =2rsin (A/2)3 .弓形高 h=r-sqrt(r-2-a'2/4)=r(1-cos(A/2) =atan(A/4)/24 .扇形面积 Sl=rl/2=r"2A/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棱台: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=PIr"2h圆锥：1 .母线 !=sqrt (h 2+r*2)2 .侧面积S=PIrl3 .全面积 T=PIr(l+r)4 .体积 V=PIr"2h/3圆台:1 .母线 !=sqrt (h"2+(rl-r2) 2)2 .侧面积 S=PI(rl+r2)l3 .全面积 T=PIrl(l+rl)+PIr2(l+r2)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 <stdlib. h>#include <math. h>#define MAXN 1000#define offset 10000# define eps le-8# define zero(x) (x)>0?(x):-(x)<eps)# define _sign(x) (x)>eps?l: (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;i<n&&sl|s2;i+)s_sign(xmult(p(i+l)%n, p(i+2)%n, pi)=0;return s 1|s2;判定凸多边形,顶点按顺时针或逆时针给出,不允许相邻边共线 int is_convex_v2(int n, point* p)int i, s3 = l, 1, 1;for (i=0;i<n&&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 (xmult (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;i<n&&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, point* p, int on_edge=l)point q2;int i=0,count;while (i<n)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, q2)*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. 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;i<n;i+)if(opposite_side(11, 12, pi, p(i+l)%n)&&opposite_side(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;i<k;i+)for (j=i+l;j<k;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 intersection(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, 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;i<n-l;i+)if (fabs(t2=xmult(p0, pi, pi+l)>eps) t二barycenter(p, pi, pi+l)； ret. x+=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)struct point(double x,y;/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);/int same_side(point pl,point p2,point 11,point 12)( return xmult(11, pl, 12)*xmult(11, p2, 12)>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)/(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;i<n;i+)if (same side(pi, side, 11, 12) ppm+=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 (n<3)n=0;1.5 浮点函数浮点几何函数库#include <math. h>#define eps le-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) return (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);两点距离double 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_inline(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) returnzero(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 dot online_ex(point p, line 1)returndot online_in(p, 1)&&(!zero(p. x-1. a. x) | | !zero(p. y-1. a. y)&&(!zero(p. x-1. b. x) I | !ze ro (p. y-1, b. y);int dot online_ex (point p, point 11, point 12) returndot_online_in(p, 11, 12)&&(!zero(p. x-11. x) | | !zero(p. y-11. y) && (! zero (p. x-12. x) I ! z ero(p. y-12. y);int dot on1ine_ex(doub1e x, double y, double xl,double yl,double x2, double y2) returndot online_in(x, y, xl, yl, x2, y2)&&(!zero(x-x1)|I!zero(y-y1)&&(!zero(x-x2)|!zero( y-y2);判两点在线段同侧,点在线段上返回int same_side(point pl,point p2,line 1)return xmult (1. a, pl, 1. b)*xmult (1. a, p2, 1. b) >eps;int same_side(point pl,point p2,point 11,point 12) return xmult(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;判两直线平行int parallel(line u,line v) return zero(u. a. x-u. b. x)*(v. a. y-v. b. y)-(v. a. x-v. b. x)*(u. a. y-u. b. y);int parallel(point ul,point u2, point vl, point v2)return zero(ul. x-u2. x)*(vl. y-v2. y)-(vl. x-v2. x)*(ul. y-u2. y);判两直线垂直int perpendicular(line u, line v) return zero (u. a. x-u. b. x) * (v. a. x-v. b. x) + (u. a. y-u. b. y) * (v. a. y-v. b. y);int perpendicular(point ul,point u2, point vl,point v2) return zero(ul. x-u2. x)*(vl. x-v2. x) + (ul. y-u2. y)*(vl. y-v2. y);判两线段相交,包括端点和部分重合int intersect_in(line u, line v)if (!dots_inline(u. a, u. b, v. a) | | !dots_inline(u. a, u. b, v. b) return ! same_side (u. a, u. b, v)&&!same_side(v. a, v. b, u);returndot_online_in(u. a, v)|dot_online_in(u. b, v)|dot_online_in(v. a, u)|dot_online_in( v. b, u);int intersect_in(point ul, point u2, point vl, point v2)if (!dots_inline(ul, u2, vl)|!dots_inline(ul, u2,v2)return !same_side(ul, u2, vl, v2)&&!same_side(v1,v2,ul,u2);returndot online_in(ul,vl, v2)I|dot_online_in(u2, vl, v2)|dot_online_in(vl, ul, u2)|dot_o nline_in(v2, ul, u2);)/判两线段相交,不包括端点和部分重合int intersect ex (line u, line v)return opposite_side (u. a, u. b, v) &&opposi te_side (v. a, v. b, u);int intersect_ex(point ul, point u2, point vl, point v2) return opposite_side(ul, u2, vl, v2)&&opposite_side(v1, v2, ul, u2);计算两直线交点,注意事先判断直线是否平行!线段交点请另外判线段相交(同时还是要判断是否平行!)point intersection(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 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)/(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-u 1. y)*t;return ret;点到直线上的最近点point ptoline(point p,line 1)point t=p;t. x+=l. a. y-l. b. y, t. y+=l. b. x-l. a. x;return intersection(p, t, 1. a, 1. b);point ptoline(point p,point 11,point 12)point t=p;t. x+=ll. y-12. y, t. y+=12. x-11. x;return intersection(p,t, 11, 12);点到直线距离double disptoline(point p,line 1)return fabs(xmult (p, 1. a, 1. b)/distance(l. a, 1. b);double disptoline(point p, point 11,point 12)return fabs(xmult(p, 11, 12)/distance(ll, 12);double disptoline(double x,double y,double xl,double yl,double x2, double y2) return fabs(xmult(x, y, xl, yl, x2, y2)/distance(xl, yl, x2, y2);点到线段上的最近点point ptoseg(point p,line 1)(point t=p;t. x+=l. a. y-l. b. y, t. y+=l. b. x-l. a. x;if (xmult (1. a, t, p)*xmult (1. b, t, p) >eps)return distance(p, 1. a)<distance(p, 1. b)?l. a: 1. b;return intersection (p, t, 1. a, 1. b);point ptoseg(point p,point 11, point 12)point t=p;t. x+=ll. y-12. y, t. y+=12. x-11. x;if (xmult(11, t, p)*xmult(12, t, p)>eps)return distance(p, ll)<distance(p, 12)?11:12;return intersection(p, t, 11, 12);点到线段距离double disptoseg(point p, line 1)point t=p;t. x+=l. a. y-l. b. y, t. y+=l. b. x-l. a. x;if (xmult (1. a, t, p)*xmult (1. b, t, p) >eps