ACM模板(浙大版).pdf

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

1、目 录.几 何.41.1 注 意.41.2 几 何 公 式.41.3 多 边 形.61.4 多 边 形 切 割.91.5 浮 点 函 数.101.6 面 积.151.7 球 面.161.8 三 角 形.171.9 三 维 几 何.191.10 凸 包.271.11 网 格.281.12 圆.281.13 整 数 函 数.30,组 合.332.1 组 合 公 式.332.2 排 列 组 合 生 成.332.3 生 成 GRAY 码.352.4 置 换(PO LYA).352.5 字 典 序 全 排 列.362.6 字 典 序 组 合.36三.结 构.373.1 并 查 集.373.2 堆.383

2、.3 线 段 树.393.4 子 段 和.443.5 子 阵 和.45四.数 论.454.1 阶 乘 最 后 非。位.454.2 模 线 性 方 程 组.464.3 素 数.474.4 欧 拉 函 数.494.5 定 积 分 计 算(ROMBERG).494.6 多 项 式 求 根(牛 顿 法).514.7 周 期 性 方 程(追 赶 法).52五.图 论.535.1 NP 搜 索.5315.1.1 最 大 团.535.1.2 最 大 团（n6G（faster）.545.2 连 通 性.565.2.1 无 向 图 关 键 点（d fs邻 接 阵）.565.2.2 无 向 图 关 键 边（d f

3、s邻 接 阵）.575.2.3 无 向 图 的 块（b fs邻 接 阵）.585.2.4 无 向 图 连 通 分 支（dfs/bfs邻 接 阵）.595.2.5 有 向 图 强 连 通 分 支（dfs/bfs邻 接 阵）.605.2.6 有 向 图 最 小 点 基（邻 接 阵）.625.3 匹 酉 己.625.3.1 二 分 图 最 大 匹 配（hungary令|5 接 表）.625.3.2 二 分 图 最 大 匹 配（hungary邻 接 阵）.635.3.3 二 分 图 最 大 匹 配（hungary正 向 表）.635.3.4 二 分 图 最 佳 匹 配（kuhn_munkras邻 接

4、阵）.645.3.5 一 般 图 匹 配（邻 接 表）.655.3.6 一 般 图 匹 配（邻 接 阵）.665.3.7 一 般 图 匹 配（正 向 表）.675.4 网 络 流.685.4.1 最 大 流（邻 接 阵）.685.4.2 上 下 界 最 大 流（邻 接 阵）.695.4.3 上 下 界 最 小 流（邻 接 阵）.695.4.4 最 大 流 无 流 量（邻 接 阵）.705.4.5 最 小 费 用 最 大 流（邻 接 阵）.715.5 应 用.725.5.1 欧 拉 回 路（邻 接 阵）.725.5.2 树 的 前 序 表 转 化.725.5.3 树 的 优 化 算 法.735.

5、5.4 拓 扑 排 序（邻 接 阵）.755.5.5 最 佳 边 割 集.755.5.6 最 佳 点 割 集.765.5.7 最 小 边 割 集.785.5.8 最 小 点 割 集.795.5.9 最 小 路 径 覆 盖.805.6 支 撑 树.815.6.1 最 小 生 成 树（kruskal邻 接 表）.815.6.2 最 小 生 成 树（kruskal正 向 表）.825.6.3 最 小 生 成 树（prim+binary_heap 邻 接 表）.835.6.4 最 小 生 成 树（prim+binary_heap 正 向 表）.855.6.5 最 小 生 成 树（prim+mapped

6、_heap 邻 接 表）.865.6.6 最 小 生 成 树（prim+mapped_heap 正 向 表）.875.6.7 最 小 生 成 树（prim邻 接 阵）.885.6.8 最 小 树 形 图（邻 接 阵）.895.7 最 短 路 径.905.7.1 最 短 路 径（单 源 bellman_ford邻 接 阵）.9025.7.2 最 短 路 径（单 源 dijkstra+bfs邻 接 表）.915.7.3 最 短 路 径（单 源 dijkstra+bfs正 向 表）.915.7.4 最 短 路 径（单 源 dijkstra+binary_heap 邻 接 表）.925.7.5 最 短

7、 路 径（单 源 dijkstra+binary_heap 正 向 表）.935.7.6 最 短 路 径（单 源 dijkstra+m叩 ped_heap邻 接 表）.945.7.7 最 短 路 径（单 源 dijkstra+mapped_heap正 向 表）.955.7.8 最 短 路 径（单 源 dijkstra邻 接 阵）.965.7.9 最 短 路 径（多 源 floyd_warshall邻 接 阵）.97六.应 用.986.1 Joseph 问 题.986.2 N 皇 后 构 造 解.986.3 布 尔 母 函 数.996.4 第 k 元 素.1006.5 幻 方 构 造.1006.

8、6 模 式 匹 配（kmp）.1016.7 逆 序 对 数.1026.8 字 符 串 最 小 表 示.1026.9 最 长 公 共 单 调 子 序 列.1036.1 0 最 长 子 序 列.1046.1 1 最 大 子 串 匹 配.1056.1 2 最 大 子 段 和.1066.1 3 最 大 子 阵 和.107七.其 它.1087.1 大 数（只 能 处 理 正 数）.1087.2 分 数.1137.3 矩 阵.1157.4 线 性 方 程 组.1177.5 线 性 相 关.1197.6 日 期.1203几 何 1.1注 意 1.注 意 舍 入 方 式(0.5的 舍 入 方 向);防 止 输

9、 出-0.2.儿 何 题 注 意 多 测 试 不 对 称 数 据.3.整 数 儿 何 注 意 xm ult和 dm ult是 否 会 出 界；符 点 几 何 注 意 e p s的 使 用.4.避 免 使 用 斜 率;注 意 除 数 是 否 会 为 0.5.公 式 一 定 要 化 简 后 再 代 入.6.判 断 同 一 个 2*PI域 内 两 角 度 差 应 该 是 abs(a 1-a2)pi+pi-beta;相 等 应 该 是 abs(a l-a2)pi+pi-eps;7.需 要 的 话 尽 量 使 用 atan2,注 意:atan2(0,0)=0,atan2(1,0)=pi/2,atan2(

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

11、A2+cA2)-aA2)/2=sqrt(bA2+cA2+2bccos(A)/24.角 平 分 线 Ta=sqrt(bc(b+c)A2-aA2)/(b+c)=2bccos(A/2)/(b+c)5.高 线 Ha=bsin(C)=csin(B)=sqrt(bA2-(aA2+bA2-cA2)/(2a)A2)46.内 切 圆 半 径 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/(

12、2sin(A)=b/(2sin(B)=c/(2sin(C)四 边 形：D1,D2为 对 角 线,M 对 角 线 中 点 连 线,A 为 对 角 线 夹 角 1.aA2+bA2+cA2+dA2=D 1A2+D2A2+4MA22.S=DlD2sin(A)/2(以 卜 对 圆 的 内 接 四 边 形)3.ac+bd=D 1D24.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(RA2-rA2)=2Rsin(A/2

13、)=2rtan(A/2)4.面 积 S=nar/2=nrA2tan(A/2)=nRA2sin(A)/2=naA2/(4tan(A/2)圆：1.弧 长 l=rA2.弦 长 a=2sqrt(2hr-hA2)=2rsin(A/2)3.弓 形 高 h=r-sqrtr2-aA2/4)=r(l-cos(A)=atan(A/4)/24.扇 形 面 积 Sl=rl/2=rA2A/25.弓 形 面 积 S2=(rl-a(r-h)/2=rA2(A-sin(A)/2棱 柱：1.体 积 V=Ah,A为 底 面 积,h 为 高 2.侧 面 积 S=lp,l为 棱 长,p 为 直 截 面 周 长 3.全 面 积 T=S+

14、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+A25圆 柱:1.侧 面 积 S=2PIrh2.全 面 积 T=2PIr(h+r)3.体 积 V=PIrA2h圆 锥：1.母 线 l=sqrt(hA2+

15、rA2)2.侧 面 积 S=PIrl3.全 面 积 T=PIr(l+r)4.体 积 V=P1rA2h/3圆 台：1.母 线 l=sqrt(hA2+(rl-r2)A2)2.侧 面 积 S=PI(rl+r2)l3.全 面 积 T=PIrl(l+rl)+PIr2(l+r2)4.体 积 V=PI(r 1 A2+r2A2+r 1 r2)h/3球：L 全 面 积 T=4PIrA22.体 积 V=4PIrA3/3球 台：1.侧 面 积 S=2PIrh2.全 面 积 T=PI(2rh+rl 八 2+r2A2)3.体 积 V=PIh(3(rl A2+r2A2)+hA2)/6球 扇 形：1.全 面 积 T=PIr

16、(2h+rO),h为 球 冠 高,rt)为 球 冠 底 面 半 径 2.体 积 V=2PIrh/31.3多 边 形#include#inciude#define MAXN 1 000#define offset 10000#define eps le-8#define zero(x)(x)0?(x):-(x)eps?1:(x)-eps?2:0)struct point double x,y;struct line point a,b;double xmult(point pinpoint p2,point p0)return(pl.x-pO.x)*(p2.y-pO.y)-(p2.x-pO.x)

17、*(pl.y-p0.y);6 判 定 凸 多 边 形,顶 点 按 顺 时 针 或 逆 时 针 给 出，允 许 相 邻 边 共 线 int is_convex(int n,point*p)int i,s3=M J；for(i=0;in&slls2;i+)s_sign(xmult(p(i+l)%n,p(i+2)%n,pi)=0;return slls2;)判 定 凸 多 边 形,顶 点 按 顺 时 针 或 逆 时 针 给 出，不 允 许 相 邻 边 共 线 int is_convex_v2(int n,point*p)int i,s3=1,1,1)；for(i=0;in&s0&slls2;i+)s

18、Lsign(xmult(p(i+l)%n,p(i+2)%n,pi)=0;return s0&slls2;判 点 在 凸 多 边 形 内 或 多 边 形 边 上，顶 点 按 顺 时 针 或 逆 时 针 给 出 int inside_convex(point q,int n,point*p)int i,s3=M J；for(i=0;in&slls2;i+)sLsign(xmult(p(i+1)%n,q,pi)=0;return slls2;)判 点 在 凸 多 边 形 内，顶 点 按 顺 时 针 或 逆 时 针 给 出，在 多 边 形 边 上 返 回 0int inside_convex_v2(p

19、oint q,int n,point*p)inti,s3=U,l；for(i=0;in&s0&slls2;i+)s_sign(xmult(p(i+1)%n,q,pi)J=0;return s0&slls2;判 点 在 任 意 多 边 形 内，顶 点 按 顺 时 针 或 逆 时 针 给 出/on_edge表 示 点 在 多 边 形 边 上 时 的 返 回 值,offset为 多 边 形 坐 标 上 限 int inside_polygon(point q,int n,point*p,int on_edge=l)point q2;int i=0,count;while(in)for(count=i

20、=0,q2.x=rand()4-offset,q2.y=rand()+offset;in;i+)if(zero(xmult(q,pi,p(i+1)%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)7return on_edge;else if(zero(xmult(q,q2,pi)break;else if(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 cou

21、nt&l;)inline int opposite_side(point pl,point p2,point 11,point 12)return xmult(ll,pl,12)*xmult(ll,p2,12)-eps;)inline int dot_online_in(point p,point 11,point 12)return zero(xmult(p,ll,12)&(11.x-p.x)*(12.x-p.x)eps&(!1.y-p.y)*(12.y-p.y)eps;)判 线 段 在 任 意 多 边 形 内,顶 点 按 顺 时 针 或 逆 时 针 给 出，与 边 界 相 交 返 回 1i

22、nt inside_polygon(point 11,point 12,int n,point*p)point tMAXN,tt;int i,j,k=O;if(!inside_polygon(ll,n,p)ll!inside_polygon(12,n,p)return 0;for(i=0;in;i+)if(opposite_side(ll,12,pi,p(i4-l)%n)&opposite_side(pi,p(i+l)%n,ll,12)return 0;else if(dot_online_in(l 1,pi,p(i+1)%n)tk+=ll;else if(dot_online_in(12,p

23、i,p(i+l)%n)tk+=12;else if(dot_online_in(pi,ll,12)tk+=pi;for(i=0;ik;i+)for(j=i+l;jk;j+)tt.x=(ti.x+tj.x)/2;tt.y=(ti.y+t|jJ.y)/2;if(!inside_polygon(tt,n,p)return 0;)return 1;point intersection(line u,line v)8point 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

24、.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;itb=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)po

25、int ret,t;double tl=0,t2;int i;ret.x=ret.y=O;for(i=l;ieps)t=barycenter(pO,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)9struct point double x,y;double xmul

26、t(point pl,point p2,point p0)return(pl.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(pl.y-pO.y);)int same_side(point pl,point p2,point 11,point 12)return xmult(ll,pl,12)*xmult(ll,p2,12)eps;)point intersection(point ul,point u2,point v 1,point v2)point ret=u 1;double t=(u 1.x-v 1.x)*(v 1.y-v2.y)-(u l.y-v l.y)*(v

27、l.x-v2.x)/(u 1.x-u2.x)*(v 1.y-v2.y)-(u 1.y-u2.y)*(v l.x-v2.x);ret.x+=(u2.x-u l.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,l 1,1

28、2)ppm+=pi;if(!same_side(pi,p(i+l)%n,ll,12)&!(zero(xmult(pi,ll,12)&zero(xmult(p(i+l)%n,ll,12)ppm+=intersection(pi,p(i+l)%n,ll,12);)for(n=i=0;im;i+)if(!ill!zero(ppi.x-ppi-l.x)ll!zero(ppi.y-ppi-l.y)pn+=ppi;if(zero(pn-1.x-p0.x)&zero(pn-1.y-p0.y)n-;if(n3)n=0;)1.5浮 点 函 数 浮 点 儿 何 函 数 库#include#define eps l

29、e-810#define zero(x)(x)0?(x):-(x)eps)struct point double x,y;);struct line point a,b;计 算 cross product(Pl-P0)x(P2-P0)double xmult(point pinpoint p2,point p0)return(p l.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p l.y-pO.y);)double xmult(double xl,double yl,double x2,double y2,double xO,double y0)return(xl-x0)

30、*(y2-y0)-(x2-x0)*(y 1-yO);)计 算 dot product(Pl-P0).(P2-P0)double dmult(point pl,point p2,point p0)return(p 1.x-p0.x)*(p2.x-p0.x)+(p 1.y-p0.y)*(p2.y-p0.y);1double dmult(double xl,double yl,double x2,double y2,double xO,double y0)return(xl-x0)*(x2-x0)+(yl-y0)*(y2-y0);)两 点 距 离 double distance(point pl,p

31、oint p2)return sqrt(pl.x-p2.x)*(p l.x-p2.x)+(pl.y-p2.y)*(pl.y-p2.y);)double distance(double xl,double yl,double x2,double y2)return sqrt(x 1-x2)*(x 1-x2)+(y l-y2)*(y 1-y2);)判 三 点 共 线 int dots_inline(point pl,point p2,point p3)return zero(xmult(p 1,p2,p3);)int dots_inline(double xl,double yl,double x

32、2,double y2,double x3,double y3)return zero(xmult(x l,y 1,x2,y2,x3,y3);)判 点 是 否 在 线 段 上，包 括 端 点 int dot_online_in(point p,line 1)return zero(xmult(p,l.a,l.b)&(l.a.x-p.x)*(l.b.x-p.x)eps&(l.a.y-p.y)*(l.b.y-p.y)eps;)int dot_online_in(point p,point 11,point 12)return zero(xmult(p,Il,12)&(11.x-p.x)*(12.x

33、-p.x)eps&(l 1.y-p.y)*(12.y-p.y)eps;)int dot_online_in(double x,double y,double xl,double yl,double x2,double y2)11return zero(xmult(x,y,x l,y I,x2,y2)&(x 1-x)*(x2-x)eps&(y 1-y)*(y2-y)eps;)int same_side(point pl,point p2,point 11,point 12)return xmult(ll,p 1,12)*xmult(l 1,p2,12)eps;判 两 点 在 线 段 异 侧，点

34、在 线 段 上 返 回 0int opposite_side(point pl,point p2,line 1)return xmult(l.a,p 1,l.b)*xmult(l.a,p2,l.b)-eps;)int opposite_side(point pl,point p2,point 11,point 12)return xmult(ll,p 1,12)*xmult(l 1,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.

35、a.y-u.b.y);)int parallel(point ul,point u2,point vl,point v2)return zero(u 1.x-u2.x)*(vl.y-v2.y)-(vl.x-v2.x)*(u 1.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);12ini perpendicular(point ul,point u2,point vl,point v2)return zero

36、(u 1.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)ll!dots_inline(u.a,u.b,v.b)return!same_side(u.a,u.b,v)&!same_side(v.a,v.b,u);retum dot_online_in(u.a,v)lldot_online_in(u.b,v)lldot_online_in(v.a5u)lldot_online_i

37、n(v.b,u);)int intersect_in(point ul,point u2,point vl,point v2)if(!dots_inline(u l,u2,v l)ll!dots_inline(u I,u2,v2)return!same_side(u 1,u2,vl,v2)&!same_side(vl,v2,ul,u2);returndot_online_in(u l,v 1,v2)lldot_online_in(u2,v 1,v2)lldot_online_in(v I,ul,u2)lldot_online_in(v2,u 1,u2)；)判 两 线 段 相 交，不 包 括 端

38、 点 和 部 分 重 合 int intersect_ex(line u,line v)return opposite_side(u.a,u.b,v)&opposite_side(v.a,v.b,u);)int intersect_ex(point u 1,point u2,point vl,point v2)return opposite_side(u l,u2,v 1,v2)&opposite_side(v l,v2,u l,u2);)计 算 两 直 线 交 点，注 意 事 先 判 断 直 线 是 否 平 行！线 段 交 点 请 另 外 判 线 段 相 交(同 时 还 是 要 判 断 是

39、否 平 行!)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 上.x-u.a.x)*t;ret.y+=(u.b.y-u.a.y)*t;retum ret;)point intersection(point ul,point u2,point vl,point v2)point ret=u 1

40、;double t=(ul.x-vl.x)*(vl.y-v2.y)-(ul.y-vl.y)*(vl.x-v2.x)/(u l.x-u2.x)*(v 1.y-v2.y)-(u 1.y-u2.y)*(v I.x-v2.x);ret.x+=(u2.x-u l.x)*t;ret.y+=(u2.y-u l.y)*t;retum ret;13 点 到 直 线 上 的 最 近 点 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,l.a,l.b);)point pt

41、oline(point p,point 11,point 12)point t=p;t.x+=l 1.y-12.y,t.y+=12.x-l 1.x;return intersection(p,t,l 1,12);)点 到 直 线 距 离 double disptoline(point p,line 1)return fabs(xmult(p,l.a,l.b)/distance(l.a,Lb);)double disptoline(point p,point 11,point 12)return fabs(xmult(p,ll,12)/distance(ll,12);)double dispto

42、line(double x,double y,double xl,double yl,double x2,double y2)return fabs(xmult(x,y,x l,y 1,x2,y2)/distance(xl,y I,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(l.a,t,p)*xmult(Lb,t,p)eps)return distance(p,l.a)eps)return distance(p,l 1)dist

43、ance(p,12)?l 1:12;return intersection(p,t,l 1,12);点 到 线 段 距 离 double disptoseg(point p,line 1)point t=p;14t.x+=l.a.y-l.b.y,t.y+=l.b.x-l.a.x;if(xmult(l.a,t,p)*xmult(l.b,l,p)eps)return distance(p,l.a)eps)return distance(p,l 1)distance(p,12)?distance(p,l 1):distance(p,12);return fabs(xmult(p,l 1,12)/di

44、stance(l 1,12);)矢 量 V 以 P 为 顶 点 逆 时 针 旋 转 angle并 放 大 scale倍 point rotate(point v,point p,double angle,double scale)point ret=p;v.x-=p.x,v.y-=p.y;p.x=scale*cos(angle);p.y=scale*sin(angle);ret.x+=v.x*p.x-v.y*p.y;ret.y+=v.x*p.y+v.y*p.x;return ret;)1.6面 积#include struct point double x,y;计 算 cross produc

45、t(Pl-P0)x(P2-P0)double xmult(point pinpoint p2,point p0)return(pl.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(pl.y-pO.y);)double xmult(double x 1,double yl,double x2,double y2,double xO,double y0)return(x l-x0)*(y2-y0)-(x2-x0)*(y 1-yO);)计 算 三 角 形 面 积，输 入 三 顶 点 double area_tnangle(point pl,point p2,point p3)ret

46、urn fabs(xmult(p 1,p2,p3)/2;)double area_triangle(double x 1,double y 1,double x2,double y2,double x3,double y3)return fabs(xmult(x l,y l,x2,y2,x3,y3)/2;)15 计 算 三 角 形 面 积，输 入 三 边 长 double area_triangle(double a,double b,double c)double s=(a+b+c)/2;return sqrt(s*(s-a)*(s-b)*(s-c);)计 算 多 边 形 面 积,顶 点 按

47、 顺 时 针 或 逆 时 针 给 出 double area_polygon(int n,point*p)double sl=0,s2=0;int i;for(i=0;in;i+)sl4-=p(i+l)%n.y*pi.x,s2+=p(i+l)%n.y：5：p(i+2)%n.x;return fabs(sl-s2)/2;)1.7球 面#include const double pi=acos(-l);计 算 圆 心 角 la t表 示 纬 度,-90v=w=pi+pi)dlng-=pi+pi;if(dlngpi)dlng=pi4-pi-dlng;latP=pi/180Jat2*=pi/180;r

48、eturn acos(cos(lat 1)*cos(lat2)*cos(dlng)+sin(lat 1)*sin(lat2);)计 算 距 离,r 为 球 半 径 double line_dist(double r,double Ing 1,double lat 1,double lng2,double lat2)double dlng=fabs(lng 1 ng2)*pi/180;while(dlng=pi+pi)dlng-=pi+pi;if(dlngpi)dlng=pi+pi-dlng;latl*=pi/180,lat2*=pi/180;return r*sqrt(2-2*(cos(lat

49、l)*cos(lat2)*cos(dlng)+sin(latl)*sin(lat2);16 计 算 球 面 距 离,r 为 球 半 径 inline double sphere_dist(double redouble Ing 1,double latl,double Ing2,double lat2)return r*angle(lngI,latl,lng2,lat2);)1.8三 角 形#include struct point double x,y;struct line point a,b;double distance(point pl,point p2)return sqrt(pl

50、.x-p2.x)*(pl.x-p2,x)+(pl.y-p2.y)*(pl.y-p2.y);)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 circumcenter(point