《ACM模板(浙大版)》由会员分享，可在线阅读，更多相关《ACM模板(浙大版)（121页珍藏版）》请在金锄头文库上搜索。
1、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 子阵和.4
2、5 四数论四数论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) ret.x/=t1,ret.y/=t1; return ret; 1.4 多边形切割多边形切割 /多边形切割 /可用于半平面交 #define MAXN 100 #define eps 1e-8 #define
3、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.y)-(u1.y-u2.y)*(v1.x-v2.x); ret.x+=(u2.x-u1.x)*t; ret.y+=(u2.y-u1.y)*t; return ret; /将多边形沿 l1,l2 确定的直线切割在 side 侧切割,保证 l1,l2,s
4、ide 不共线 void polygon_cut(int int m=0,i; for (i=0;i0?(x):-(x)eps; /判两点在线段异侧,点在线段上返回 0 int opposite_side(point p1,point p2,line l) return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)pi) dlng=pi+pi-dlng; lat1*=pi/180,lat2*=pi/180; return acos(cos(lat1)*cos(lat2)*cos(dlng)+sin(lat1)*sin(lat2); /计算距离,r 为球半径 doubl
5、e line_dist(double r,double lng1,double lat1,double lng2,double lat2) double dlng=fabs(lng1-lng2)*pi/180; while (dlng=pi+pi) dlng-=pi+pi; if (dlngpi) dlng=pi+pi-dlng; lat1*=pi/180,lat2*=pi/180; return r*sqrt(2-2*(cos(lat1)*cos(lat2)*cos(dlng)+sin(lat1)*sin(lat2); /计算球面距离,r 为球半径 inline double sphere_
6、dist(double r,double lng1,double lat1,double lng2,double lat2) 17 return r*angle(lng1,lat1,lng2,lat2); 1.8 三角形三角形 #include struct pointdouble x,y; struct linepoint a,b; double distance(point p1,point p2) return sqrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y); point intersection(line u,line v) po
7、int 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 circumcenter(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.x=u.
8、a.x-a.y+b.y; u.b.y=u.a.y+a.x-b.x; v.a.x=(a.x+c.x)/2; v.a.y=(a.y+c.y)/2; v.b.x=v.a.x-a.y+c.y; v.b.y=v.a.y+a.x-c.x; return intersection(u,v); /内心 point incenter(point a,point b,point c) line u,v; double m,n; u.a=a; m=atan2(b.y-a.y,b.x-a.x); n=atan2(c.y-a.y,c.x-a.x); u.b.x=u.a.x+cos(m+n)/2); 18 u.b.y=u
9、.a.y+sin(m+n)/2); v.a=b; m=atan2(a.y-b.y,a.x-b.x); n=atan2(c.y-b.y,c.x-b.x); v.b.x=v.a.x+cos(m+n)/2); v.b.y=v.a.y+sin(m+n)/2); return intersection(u,v); /垂心 point perpencenter(point a,point b,point c) line u,v; u.a=c; u.b.x=u.a.x-a.y+b.y; u.b.y=u.a.y+a.x-b.x; v.a=b; v.b.x=v.a.x-a.y+c.y; v.b.y=v.a.y+
10、a.x-c.x; return intersection(u,v); /重心 /到三角形三顶点距离的平方和最小的点 /三角形内到三边距离之积最大的点 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 fermentpoint(point a,point b,
11、point c) point u,v; double step=fabs(a.x)+fabs(a.y)+fabs(b.x)+fabs(b.y)+fabs(c.x)+fabs(c.y); int i,j,k; u.x=(a.x+b.x+c.x)/3; u.y=(a.y+b.y+c.y)/3; while (step1e-10) 19 for (k=0;k0?(x):-(x)eps; int same_side(point3 p1,point3 p2,point3 l1,point3 l2) return dmult(xmult(subt(l1,l2),subt(p1,l2),xmult(subt
12、(l1,l2),subt(p2,l2)eps; /判两点在线段异侧,点在线段上返回 0,不共面无意义 int opposite_side(point3 p1,point3 p2,line3 l) return dmult(xmult(subt(l.a,l.b),subt(p1,l.b),xmult(subt(l.a,l.b),subt(p2,l.b)eps; /判两点在平面异侧,点在平面上返回 0 int opposite_side(point3 p1,point3 p2,plane3 s) return dmult(pvec(s),subt(p1,s.a)*dmult(pvec(s),sub
13、t(p2,s.a)0?(x):-(x)0?1:-1):(ret0?1:-1); void _graham(int n,point* p,int for (p1=p2=p0,i=1;ieps|(zero(p1.y-pi.y) p2.x/=n,p2.y/=n; pk=p0,p0=p1; qsort(p+1,n-1,sizeof(point),graham_cp); for (ch0=p0,ch1=p1,ch2=p2,s=i=3;i2s-); /构造凸包接口函数,传入原始点集大小 n,点集 p(p 原有顺序被打乱!) /返回凸包大小,凸包的点在 convex 中 /参数 maxsize 为 1 包含
14、共线点,为 0 不包含共线点,缺省为 1 /参数 clockwise 为 1 顺时针构造,为 0 逆时针构造,缺省为 1 /在输入仅有若干共线点时算法不稳定,可能有此类情况请另行处理! /不能去掉点集中重合的点 int graham(int n,point* p,point* convex,int maxsize=1,int dir=1) point* temp=new pointn; int s,i; _graham(n,p,s,temp); for (convex0=temp0,n=1,i=(dir?1:(s-1);dir?(i0?(x):-(x) struct pointint x,y;
15、 int gcd(int a,int b) return b?gcd(b,a%b):a; /多边形上的网格点个数 int grid_onedge(int n,point* p) int i,ret=0; for (i=0;i-eps; t.x+=l1.y-l2.y; t.y+=l2.x-l1.x; return xmult(l1,c,t)*xmult(l2,c,t)0; /判两点在直线异侧,点在直线上返回 0 32 int opposite_side(point p1,point p2,line l) return sign(xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b
16、)=0;j-) if (pj0?1:-1) #define abs(x) (x)0?(x):-(x) #define _ufind_run(x) for(;pt=abs(x);x=sig(x)*pabs(x),pt=sig(pt)*(pabs(x)?pabs(x):abs(pt) #define _run_both _ufind_run(i);_ufind_run(j) #define _set_side(x) pabs(i)=sig(i)*(abs(i)=abs(j)?0:(x)*j) #define _judge_side(x) (i=(x)*j void init()memset(p,0,sizeof
