浙江大学acm模板.pdf

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

1、Z h e j i a n g U n i v e r s i t y 浙江大学 A C M 模板1 几何.31.1 注意31.4多边形切割.81.7 球面.1 51.1 0 凸包.2 61.1 3 整数函数.3 02、组合.322.1组合公式.3 22.4 置换（p o l y a）3 53、数据结构.363.1并查集.3 63.4子段和.4 34、数论.454.1阶乘最后非0 位.4 54.4 欧拉函数.4 85、数值计算.485.1定积分计算（R o m b e r g）4 86,图论一NP搜索.526.1最大团.5 27、图论一连通性.551.2几何公式.31.5 浮点函数.91.8

2、三角形.1 61.1 1 网格.2 72.2排列组合生成.3 32.5字典序全排列.3 53.2 堆.3 73.5子阵和.4 44.2模线性方程组.4 55.2 多项式求根（牛顿法）5 06.2 最大团大 6 4）（f a s t e r）1.3 多边形.51.6 面积.1 41.9 三维几何.1 81.1 2 圆.2 92.3 生成 g r a y 码.3 52.6字典序组合.3 63.3线段树.3 94.3 素数.4 75.3周期性方程（追赶法）5 17.1无向图关键点（d f s 邻接阵）5 57.3 无向图的块（b f s 邻接阵）5 77.5 有向图强连通分支（d f s/b f s

3、 邻接阵）5 87.2 无向图关键边（d f s 邻接阵）5 67.4 无向图连通分支（d f s/b f s 邻接阵）5 87.6 有向图最小点基（邻接阵）6 08、图论一匹配.608.1二分图最大匹配（h u n g a r y 邻接表）6 08.2二分图最大匹配（h u n g a r y 邻接阵）6 18.3二分图最大匹配（h u n g a r y 正向表）6 1 8.4二分图最佳匹配（k u h n j n u n k r a s 邻接阵）6 28.5 一般图匹配（邻接表）6 3 8.6 一般图匹配（邻接阵）6 4 8.7 一般图匹配（正向表）6 59、图论一网络流.669.1 最

4、大流（邻接阵）6 6 9.2上下界最大流（邻接阵）6 6 9.3上下界最小流（邻接阵）6 79.4 最大流无流量（邻接阵）6 89.5 最小费用最大流（邻接阵）6 810、图论一应用.6 91 0.1欧拉回路（邻接阵）6 91 0.4 拓扑排序（邻接阵）7 21 0.7 最小边割集.7 511、图论一支撑树.781 0.2树的前序表转化.7 01 0.5最佳边割集.7 31 0.8 最小点割集.7 61 0.3 树的优化算法.7 11 0.6最佳点割集.7 41 0.9最小路径覆盖.7 71 1.1最小生成树（k r u s k a l 邻接表）7 81 1.2 最小生成树（k r u s k

5、 a l 正向表）7 91 1.3 最小生成树（p r i m+b i n a r y _ h e a p 邻接表）811 1.4最小生成树（p r i m+b i n a r y _ h e a p 正向表）821 1.5 最小生成树（p r i m+m a p p e d _ h e a p 邻接表）831 1.6最小生成树（p r i m+m a p p e d _ h e a p 正向表）841 1.7 最小生成树（p r i m 邻接阵）85 1 1.8最小树形图（邻接阵）8612、图论一最短路径.881 2.1最短路径（单源b e l l m a n _ f o r d 邻接阵）8

6、81 2.2最短路径（单源d i j k s t r a+b f s 邻接表）881 2.3最短路径（单源d i j k s t r a+b f s 正向表）891 2.4最短路径（单源d i j k s t r a+b i n a r y h e a p 邻接表）891 2.5 最短路径（单源 d i j k s t r a+b i n a r y _ h e a p 正向表）901 2.6最短路径（单源d i j k s t r a+m a p p e d h e a p 邻接表）911 2.7 最短路径（单源 d i j k s t r a+m a p p e d _ h e a p 正

7、向表）931 2.8 最短路径（单源d i j k s t r a 邻接阵）941 2.9 最短路径（多源f l o y d _ w a r s h a l l 邻接阵）9413、应用.951 3.1 J o s e p h 问题.951 3 .4 第 k 元素.971 3 .7 逆序对数.991 3.1 0 最长子序列.1 0 11 3.1 3 最大子阵和.1 0 314、其它.1041 4.1大数（只能处理正数）1 4.4 线性方程组.1 1 41 3.2 N皇后构造解.961 3.5幻方构造.971 3.8字符串最小表示.991 3.1 1 最大子串匹配.1 0 21 3.3布尔母函数.

8、961 3.6 模式匹配（k m p）991 3.9 最长公共单调子序列.1 0 01 3.1 2 最大子段和.1 0 31 0 4 1 4.2 分数.1 1 01 4.5 线性相关.1 4.3 矩阵.1 1 21 4.6 日期.1 1 61、几何1.1注意1 .注意舍入方式(0.5的舍入方向)；防止输出-0.2 .儿何题注意多测试不对称数据.3 .整数几何注意x m u l t和d m u l t是否会出界；符点几何注意e p s的使用.4 .避免使用斜率;注意除数是否会为0.5 .公式一定要化简后再代入.6 .判断同一个2*PI域内两角度差应该是a b s(a l-a 2)b e t a|

9、a b s(a l-a 2)p i+p i-b e t a;相等应该是a b s(a l-a 2)e p s|a b s(a l-a 2)p i+p i-e p s;7 .需要的话尽量使用atan 2,注意:atan 2(0,0)=0,atan 2(l,0)=p i/2,atan 2(-1,0)=-p i/2,atan 2 (0,1)=0,atan 2(0,-l)=p i.8 .c r o s s p r o d u c t=|u|*|v*s i n(a)d o t p r o d u c t=|u|*|v *c o s(a)9 .(P l-P 0)x(P 2-P 0)结果的意义：正：P O,

10、P 1 在P 0,P 2 顺时针(0,p i)内负：P 0,P l在 P 0,P 2 逆时针(0,p i)内0 :P 0,P l,P 0,P 2 共线,夹角为。或 p i1 0 .误差限缺省使用le-8!1.2 几何公式三角形：1 .半周长 P=(a+b+c)/22.面 积 S=aH a/2=abs i n(C)/2=s q r t(P(P-a)(P-b)(P-c)3 .中线 Ma=s q r t(2 (b 2+c 2)-a 2)/2=s q r t(b2+c 2+2 bc c o s (A)/24 .角平分线 Ta=s q r t(be (b+c)2-a-2)/(b+c)=2 bc c o

11、s (A/2)/(b+c)5 .高线 H a=bs i n (C)=c s i n (B)=s q r t(b*2-(a*2+b2c2)/(2 a)2)6 .内切圆半径 r=S/P=as i n (B/2)s i n (C/2)/s i n (B+C)/2)=4 Rs i n(A/2)s i n(B/2)s i n(C/2)=s q r t(P-a)(P-b)(P-c)/P)=P tan(A/2)tan(B/2)tan(C/2)7 .外接圆半径 R=abc/(4 S)=a/(2 s i n(A)=b/(2 s i n(B)=c/(2 s i n(C)四边形：D I,D 2为对角线,M对角线中点

12、连线,A为对角线夹角1.a*2+b2+c*2+d 2=D 1 2+D 2 2+4 M22.S=D lD 2 s i n(A)/2(以下对圆的内接四边形)3.ac+bd=D lD 24.S=s q r t(P-a)(P-b)(P-c)(P-d),P 为半周长正 n 边形：R 为外接圆半径,r为内切圆半径1 .中心角A=2 P I/n2 .内角 C=(n-2)P I/n3 .边长 a=2 s q r t(R 2-r *2)=2 Rs i n (A/2)=2 r tan (A/2)4,面积 S=n ar/2=n r _2 tan (A/2)=n R 2 s i n (A)/2=n a 2/(4 ta

13、n (A/2)圆：1 .弧 长 l=r A2 .弦长 a=2 s q r t(2 h r-h _2)=2 r s i n(A/2)3 .弓形高 h=r-s q r t(r 2-a*2/4)=r(1-c o s(A/2)=atan(A/4)/24 .扇形面积 Sl=r l/2=r*2 A/25 .弓形面积 S2=(r 1 -a(r-h)/2=r 2 (A-s i n (A)/2棱柱：1 .体 积 V=A h,A 为底面积,h为高2 .侧 面 积 S=lp,1 为棱长,p为直截面周长3 .全 面 积 T=S+2 A棱锥：1 .体 积 V=A h/3,A 为底面积,h 为高(以下对正棱锥)2 .侧

14、面 积 S=lp/2,1 为斜高,p为底面周长3 .全 面 积 T=S+A棱台：1 .体积 V=(A l+A 2+s q r t(A lA 2)h/3,A l.A 2 为上下底面积,h 为高(以下为正棱台)2 .侧 面 积 S=(p l+p 2)l/2,p l.p 2 为上下底面周长,1 为斜高3 .全面积 T=S+A 1+A 2圆柱：1 .侧 面 积 S=2 P I r h2 .全面积 T=2 P I r(h+r)3 .体积 V=P I r 2 h圆锥：1,母线 l=s q r t(h 2+r 2)2 .侧 面 积 S=P I r l3 .全面积 T=P I r(l+r)4 .体积 V=P

15、I r _2 h/3圆台：1.母 线 l=s q r t(h 2+(r l-r 2)2)2 .侧面积 S=P I(r l+r 2)l3 .全面积 T=P I r l(l+r l)+P I r 2(l+r 2)4 .体积 V=P I(r r 2+r 2 2+r lr 2)h/3球：1 .全面积 T=4 P I r-22 .体积 V=4 P l/3/3球台：1 .侧 面 积S=2 P I r h2 .全面积 T=P I(2 r h+r2+r 2-2)3 .体积 V=P I h(3(r r 2+r 2 c 2)+丁2)/6球扇形：1 .全 面 积T=P I r(2 h+r O),h为球冠高,r O为

16、球冠底面半径2 .体积 V=2 P I d 2 h/31 .3多边形#i n c lu d e#i n c lu d e#d e fi n e MA XN 1 0 0 0#d e fi n e o ffs e t 1 0 0 0 0#d e fi n e e p s le-8#d e fi n e z e r o (x)(x)0?(x):-(x)e p s?l:(x)-e p s?2:0)s tr u c t p o i n t d o u ble x,y;s tr u c t li n e p o i n t a,b;/d o u ble x mu lt(p o i n t p l,p o

17、i n t p 2,p o i n t p O)r e tu r n (p l.x-p 0.x)*(p 2.y-p O.y)-(p 2.x-p 0.x)*(p l.y-p 0.y);)/判定凸多边形,顶点按顺时针或逆时针给出，允许相邻边共线i n t i s _c o n v e x(i n t n,p o i n t*p)i n t i,s 3 =l,1,1 ;fo r (i=0;i n&s l I s 2 ;i+)s _s i gn(x mu lt(p(i+l)%n ,p(i+2)%n ,p i )=0;r e tu r n s l|s 2 ;)判定凸多边形,顶点按顺时针或逆时针给此不允许

18、相邻边共线i n t i s _c o n v e x _v 2(i n t n,p o i n t*p)i n t i,s 3 =l,1,1 ;fo r (i=0;i n&s 0&s l s 2 ;i+)s _s i gn(x mu lt(p(i+l)%n ,p(i+2)%n ,p i )=0;r e tu r n s 0&s l|s 2 ;)判点在凸多边形内或多边形边匕 顶点按顺时针或逆时针给出i n t i n s i d e c o n v e x (p o i n t q,i n t n,p o i n t*p)i n t i,s 3 =l,1,1 ;fo r (i=0;i n&,s

19、 l|s 2 ;i+)s _s i gn(x mu lt(p(i+l)%n ,q,p i )=0;r e tu r n s 1|s 2 ;)判点在凸多边形内，顶点按顺时针或逆时针给此在多边形边上返回0i n t i n s i d e c o n v e x v 2 (p o i n t q,i n t n,p o i n t*p)i n t i,s 3 =l,1,1 ;fo r (i=0;in&ss 2;i+)s _s i gn(x mu lt(p(i+l)%n ,q,p i )=0;r e tu r n s 0&s l|s 2 ;判点在任意多边形内，顶点按顺时针或逆时针给出/o n.e d

20、 ge表示点在多边形边上时的返回值,o ffs e t为多边形坐标上限i n t i n s i d e j p o lygo n(p o i n t q,i n t n,p o i n t*p,i n t o n _e d ge=l)p o i n t q 2;i n t i=0,c o u n t;wh i le (i n)fo r (c o u n t=i二0,q 2.x=r an d()+o ffs e t,q 2.y=r an d()+o ffs e t;i n;i+)i f(z e r o(x mu lt(q,p i ,p(i+l)%n )&(p i .x-q.x)*(p(i+l)

21、%n .x-q.x)e p s&(p i .y-q.y)*(p(i+l)%n .y-q.yXe p s)r e tu r n o n _e d ge;e ls e i f(z e r o(x mu lt(q,q 2,p i )br e ak;e ls ei f(x mu lt(q,p i ,q 2)*x mu lt(q,p(i+l)%n ,q 2)-e p s&x mu lt(p i ,q,p(i+1)%n )*x mu lt(p i ,q 2,p(i+l)%n )-e p s)c o u n t+;r e tu r n c o u n t&l;)i n li n e i n t o p p

22、o s i te _s i d e(p o i n t p l,p o i n t p 2,p o i n t 1 1,p o i n t 1 2)r e tu r n x mu lt(1 1,p l,1 2)*x mu lt(1 1,p 2,1 2)-e p s;i n li n e i n t d o t_o n li n e _i n(p o i n t p,p o i n t 1 1,p o i n t 1 2)r e tu r nz e r o(x mu lt(p,1 1,1 2)&(1 1.x-p.x)*(1 2.x-p.x)e p s&(ll.y-p.y)*(1 2.y-p.y)

23、e p s;)判线段在任意多边形内，顶点按顺时针或逆时针给出，与边界相交返回1i n t i n s i d e _p o lygo n(p o i n t 1 1,p o i n t 1 2,i n t n,p o i n t*p)p o i n t tMA XN,tt;i n t i,j,k=0;i f(!i n s i d e _p o lygo n(1 1,n,p)|!i n s i d e _p o lygo n(1 2,n,p)r e tu r n 0;fo r (i=0;i n;i+)i f(o p p o s i te s i d e(ll,1 2,p i ,p(i+l)%n

24、)&o p p o s i te s i d e(p i ,p(i+l)%n ,1 1,1 2)r e tu r n 0;e ls e i f(d o t o n li n e _i n(ll,p i ,p(i+l)%n )tk+=ll;e ls e i f(d o t_o n li n e _i n(1 2,p i ,p(i+l)%n )tk+=1 2;e ls e i f(d o t_o n li n e _i n(p i ,1 1,1 2)tk+=p i ;fo r (i=0;i k;i+)fo r (j=i+l;j k;j+)tt.x=(ti .x+tj .x)/2;tt.y=(ti

25、.y+tj .y)/2;i f(!i n s i d e _p o lygo n(tt,n,p)r e tu r n 0;)r e tu r n 1;)p o i n t i n te r s e c ti o n(li n e u,li n e v)p o i n t r e t=u.a;d o u ble 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);r e t.x+二(u.b.x-u.a.x)*t;r e

26、t.y+=(u.b.y-u.a.y)*t;r e tu r n r e t;)p o i n t bar yc e n te r(p o i n t a,p o i n t b,p o i n t c)li n e 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;r e tu r n i n te r s e c ti o n(u,v);)多边形重心p o i n t bar yc e n te r(i n t n,p o i n t*p)p o i n t r e

27、t,t;d o u ble 1 1=0,t2;i n t i;r e t.x=r e t.y=0;fo r (i=l;i e p s)t=bar yc e n te r(p 0 ,p i ,p i+l);r e t.x+=t.x*t2;r e t.y+=t.y*t2;tl+=t2;)i f(fabs(tl)e p s)r e t.x/=tl,r e t.y/=tl;r e tu r n r e t;)1.4 多边形切割多边形切割可用于半平面交d e fi n e MA XN 1 0 0#d e fi n e e p s le-8#d e fi n e z e r o(x)(x)0?(x)：-(

28、x)e p s;)p o i n t i n te r s e c ti o n(p o i n t u l,p o i n t u 2,p o i n t v l,p o i n t v 2)p o i n t r e t=u l;d o u ble t=(u l.x-v l.x)*(v l.y-v 2.y)-(u l.y-v l.y)*(v l.x-v 2.x)/(u l.x-u 2.x)*(v l.y-v 2.y)-(u l.y-u 2.y)*(v l.x-v 2.x);r e t.x+=(u 2.x-u l.x)*t;r e t.y+=(u 2.y-u l.y)*t;r e tu r

29、n r e t;)将多边形沿1 1,1 2确定的直线切割在s i d e侧切割，保 证1 1,1 2,s i d e不共线v o i d p o lygo n c u t(i n t&n,p o i n t*p,p o i n t 1 1,p o i n t 1 2,p o i n t s i d e)p o i n t p p 1 0 0 ;i n t m=0,i;fo r (i=0;i n;i+)i f(s ame s i d e(p i ,s i d e,1 1,1 2)p p m+=p i ;i f(!s ame _s i d e(p i ,p(i+l)%n ,1 1,1 2)&!(z

30、 e r o(x mu lt(p i ,1 1,1 2)&z e r o(x mu lt(p(i+l)%n ,H,1 2)p p m+=i n te r s e c ti o n (p i ,p(i+l)%n ,1 1,1 2);)fo r (n=i=0;i m;i+)i f(!i|!z e r o(p p i .x-p p i-l.x)|!z e r o(p p i .y-p p i-l.y)p n+=p p i ;i f(z e r o(p n-1 .x-p 0 .x)&z e r o(p n-l.y-p 0 .y)n ;i f(n 3)n=0;1.5 浮点函数浮点几何函数库#i n c

31、lu d e#d e fi n e e p s le _8#d e fi n e z e r o (x)(x)0?(x)：-(x)e p s)s tr u c t p o i n t d o u ble x,y;s tr u c t li n e p o i n t a,b;计算 c r o s s p r o d u c t(P l-P 0)x(P 2-P 0)d o u ble x mu lt(p o i n t p l,p o i n t p 2,p o i n t p O)r e tu r n (p l.x-p O.x)*(p 2.y-p O.y)-(p 2.x-p O.x)*(p l

32、.y-p O.y);)/d o u ble x mu lt(d o u ble x l,d o u ble yl,d o u ble x 2,d o u ble y2,d o u ble x O,d o u ble yO)r e tu r n (x l-x O)*(y2-y0)-(x 2-x 0)*(yl-yO);计算 d o t p r o d u c t(P 1-P 0).(P 2-P 0)d o u ble d mu lt(p o i n t p l,p o i n t p 2,p o i n t p O)r e tu r n (p l.x-p O.x)*(p 2.x-p O.x)+(p

33、 l.y-p O.y)*(p 2.y-p O.y);)/d o u ble d mu lt(d o u ble x l,d o u ble yl,d o u ble x 2,d o u ble y2,d o u ble x O,d o u ble yO)r e tu r n (x l-x O)*(x 2-x 0)+(yl-yO)*(y2-y0);)两点距离d o u ble d i s tan c e(p o i n t p l,p o i n t p 2)r e tu r n s q r t(p l.x-p 2.x)*(p l.x-p 2.x)+(p l.y-p 2.y)*(p l.y-p

34、2.y);)d o u ble d i s tan c e(d o u ble x l,d o u ble yl,d o u ble x 2,d o u ble y2)r e tu r n s q r t(x l-x 2)*(x l-x 2)+(yl-y2)*(yl-y2);)判三点共线i n t d o ts _i n li n e(p o i n t p l,p o i n t p 2,p o i n t p 3)r e tu r n z e r o(x mu lt(p l,p 2,p 3);)i n t d o ts _i n li n e(d o u ble x l,d o u ble

35、 yl,d o u ble x 2,d o u ble y2,d o u ble x 3,d o u ble y3)r e tu r n z e r o(x mu lt(x l,yl,x 2,y2,x 3,y3);)判点是否在线段匕包括端点i n t d o t_o n li n e _i n(p o i n t p,li n e 1)r e tu r nz e r o(x mu lt(p,1.a,1.b)&(l.a.x-p.x)*(l.b.x-p.x)e p s&(l.a.y-p.y)*(l.b.y-p.y)e p s)i n t d o t_o n li n e _i n(p o i n

36、t p,p o i n t 1 1,p o i n t 1 2)r e tu r nz e r o(x mu lt(p,1 1,1 2)&(1 1.x-p.x)*(1 2.x-p.x)e p s&(ll.y-p.y)*(1 2.y-p.y)e p s;)i n t d o t_o n li n e _i n(d o u ble x,d o u ble y,d o u ble x l,d o u ble yl,d o u ble x 2,d o u ble y2)r e tu r nz e r o(x mu lt(x,y,x l,yl,x 2,y2)&(x l-x)*(x 2-x)e p s&(

37、y1-y)*(y2-y)e p s;)i n t s ame _s i d e (p o i n t p l,p o i n t p 2,p o i n t 1 1,p o i n t 1 2)r e tu r n x mu lt(1 1,p l,1 2)*x mu lt(1 1,p 2,1 2)e p s;)判两点在线段异侧，点在线段上返回0i n t o p p o s i te _s i d e(p o i n t p l,p o i n t p 2,li n e 1)r e tu r n x mu lt(1.a,p l,1.b)*x mu lt(1.a,p 2,1.b)-e p s;)

38、i n t o p p o s i te _s i d e(p o i n t p l,p o i n t p 2,p o i n t 1 1,p o i n t 1 2)r e tu r n x mu lt(1 1,p l,1 2)*x mu lt(1 1,p 2,1 2)e p s)r e tu r n d i s tan c e(p,1.a)e p s)r e tu r n d i s tan c e(p,ll)e p s)returndistance(p,1.a)eps)returndistance(p,ll)distance(p,12)?distance(p,11):distance

39、(p,12);return fabs(xmult(p,11,12)/distance(ll,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 pointdouble x,y

40、;计算 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-xO)*(y2-y0)-(x2-x0)*(yl-yO);)计算三角形面积,输入三顶点double area_triangle(point pl,point p2,point p3)

41、return fabs(xmult(pl,p2,p3)/2;)double area_triangle(double xl,double yl,double x2,double y2,double x3,double y3)return fabs(xmult(xl,yl,x2,y2,x3,y3)/2;)计算三角形面积,输入三边长double area_triangle(double a,double b,double c)d o u ble s=(a+b+c)/2;r e tu r n s q r t(s*(s-a)*(s-b)*(s-c);)计算多边形面积,顶点按顺时针或逆时针给出d o u

42、 ble ar e a_p o lygo n(i n t n,p o i n t*p)d o u ble s l=0,s 2=0;i n t i;fo r (i=0;i n;i+)s l+=p(i+l)%n ,y*p i .x,s 2+=p(i+l)%n .y*p(i+2)%n .x;r e tu r n fabs(s l-s 2)/2;)1.7 球面#i n c lu d e c o n s t d o u ble p i=ac o s(-1);/计算圆心角lat表示纬度,-9 0=w=9 0,I n g表示经度返回两点所在大圆劣弧对应圆心角，0 =an gle =p i+p i)d i n

43、 g-=p i+p i;i f(d ln g p i)d i n g=p i+p i-d ln g;latl*=p i/1 8 0,lat2*=p i/1 8 0;r e tu r n ac o s(c o s(latl)*c o s(lat2)*c o s(d i n g)+s i n(latl)*s i n(lat2);)计算距离,r为球半径d o u ble li n e _d i s t(d o u ble r,d o u ble I n gl,d o u ble latl,d o u ble ln g2,d o u ble lat2)d o u ble d ln g=fabs(ln

44、gl-ln g2)*p i/1 8 0;wh i le (d ln g=p i+p i)d ln g-=p i+p i;i f(d ln g p i)d i n g=p i+p i-d ln g;latl*=p i/1 8 0,lat2*=p i/1 8 0;r e tu r n r*s q r t(2-2*(c o s(latl)*c o s(lat2)*c o s(d i n g)+s i n(latl)*s i n(lat2);)计算球面距离,r为球半径i n li n e d o u ble s p h e r e _d i s t(d o u ble r,d o u ble I n

45、gl,d o u ble latl,d o u ble ln g2,d o u blelat2)r e tu r n r*an gle(I n gl,latl,ln g2,lat2);1.8 三角形#include struct point double x,y;struct linepoint a,b;double distance(point pl,point p2)return sqrt(pl.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

46、 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.a.x-a.y+b.y;u.b.y=u.a.y+a.x-b

47、.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);u.b.y=u.a.y+sin(m+n)/2);v.a二b;m=atan2(a.y-b.y,a.x-b.x)

48、;n=atan 2(c.y-b.y,c.x-b.x);v.b.x=v.a.x+c o s (m+n)/2);v.b.y=v.a.y+s i n (m+n)/2);r e tu r n i n te r s e c ti o n (u,v);)垂心p o i n t p e r p e n c e n te r(p o i n t a,p o i n t b,p o i n t c)li n e 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+a.x-c.x;r e t

49、u r n i n te r s e c ti o n(u,v);)重心到三角形三顶点距离的平方和最小的点三角形内到三边距离之积最大的点p o i n t bar yc e n te r(p o i n t a,p o i n t b,p o i n t c)li n e 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;r e tu r n i n te r s e c ti o n (u,v);)费马点/到三角形三顶点距离之和最小的点p o i n t f e r

50、m e n t p o i n t(p o i n t a,p o i n t b,p o i n t c)p o i n t u,v;d o u b le s t e p=f a b s(a.x)+f a b s(a.y)+f a b s(b.x)+f a b s(b.y)+f a b s(c.x)+f a b s(c.y);i n t i,j,k;u.x=(a.x+b.x+c.x)/3;u.y=(a.y+b.y+c.y)/3;w h i le (s t e p le-10)f o r (k=0;k 10;s t e p/=2,k+)f o r (i=-l;i =l;i+)f o r (j=