ACM模板(浙大版)

1 目录目录 一一几何几何.4 1.1 注意.4 1.2 几何公式.4 1.3 多边形.6 1.4 多边形切割.9 1.5 浮点函数.10 1.6 面积.15 1.7 球面.16 1.8 三角形.17 1.9 三维几何.19 1.10 凸包.27 1.11 网格.28 1.12 圆.28 1.13 整数函数.30 二组合二组合.33 2.1 组合公式.33 2.2 排列组合生成 .33 2.3 生成GRAY码 .35 2.4 置换(POLYA) .35 2.5 字典序全排列 .36 2.6 字典序组合.36 三结构三结构.37 3.1 并查集.37 3.2 堆.38 3.3 线段树.39 3.4 子段和.44 3.5 子阵和.45 四数论四数论.45 4.1 阶乘最后非 0 位 .45 4.2 模线性方程组 .46 4.3 素数.47 4.4 欧拉函数.49 4.5 定积分计算(ROMBERG).49 4.6 多项式求根(牛顿法).51 4.7 周期性方程(追赶法).52 五图论五图论.53 5.1NP 搜索.53 2 5.1.1 最大团.53 5.1.2 最大团(n0?(x):-(x)eps?1:(x)-eps?2:0) struct pointdouble x,y; struct linepoint a,b; double xmult(point p1,point p2,point p0) return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); 7 /判定凸多边形,顶点按顺时针或逆时针给出,允许相邻边共线 int is_convex(int n,point* p) int i,s3=1,1,1; for (i=0;ini+) s_sign(xmult(p(i+1)%n,p(i+2)%n,pi)=0; return s1|s2; /判定凸多边形,顶点按顺时针或逆时针给出,不允许相邻边共线 int is_convex_v2(int n,point* p) int i,s3=1,1,1; for (i=0;ini+) s_sign(xmult(p(i+1)%n,p(i+2)%n,pi)=0; return s0 /判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出 int inside_convex(point q,int n,point* p) int i,s3=1,1,1; for (i=0;ini+) s_sign(xmult(p(i+1)%n,q,pi)=0; return s1|s2; /判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回 0 int inside_convex_v2(point q,int n,point* p) int i,s3=1,1,1; for (i=0;ini+) s_sign(xmult(p(i+1)%n,q,pi)=0; return s0 /判点在任意多边形内,顶点按顺时针或逆时针给出 /on_edge 表示点在多边形边上时的返回值,offset 为多边形坐标上限 int inside_polygon(point q,int n,point* p,int on_edge=1) 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+1)%n) 8 else if (zero(xmult(q,q2,pi) break; else if (xmult(q,pi,q2)*xmult(q,p(i+1)%n,q2)- eps return count inline int opposite_side(point p1,point p2,point l1,point l2) return xmult(l1,p1,l2)*xmult(l1,p2,l2)-eps; inline int dot_online_in(point p,point l1,point l2) return zero(xmult(p,l1,l2) /判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回 1 int inside_polygon(point l1,point l2,int n,point* p) point tMAXN,tt; int i,j,k=0; if (!inside_polygon(l1,n,p)|!inside_polygon(l2,n,p) return 0; for (i=0;in;i+) if (opposite_side(l1,l2,pi,p(i+1)%n) else if (dot_online_in(l1,pi,p(i+1)%n) tk+=l1; else if (dot_online_in(l2,pi,p(i+1)%n) tk+=l2; else if (dot_online_in(pi,l1,l2) tk+=pi; for (i=0;ik;i+) for (j=i+1;jeps) ret.x/=t1,ret.y/=t1; return ret; 1.4 多边形切割多边形切割 /多边形切割 /可用于半平面交 #define MAXN 100 #define eps 1e-8 #define zero(x) (x)0?(x):-(x)eps; point intersection(point u1,point u2,point v1,point v2) point ret=u1; double t=(u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x) /(u1.x-u2.x)*(v1.y-v2