別人的模板浙江大學(xué)acm

1、ACM 集訓(xùn)資料by colinICPC TeamRoutine Libraryby WishingBone (Dec. 2002)Last Update (Nov. 2004) by Riveria第 1 頁(yè)ACM 集訓(xùn)資料by colin1、幾何25注意25幾何公式25多邊形27多邊形切割30浮點(diǎn)函數(shù)31面積36球面37三角形38三維幾何40凸包47網(wǎng)格49圓49整數(shù)函數(shù)511.11.21.31.41.51.61.71.81.91.101.111.121.13第 2 頁(yè)ACM 集訓(xùn)資料by colin2、組合54組合公式54排列組合生成54生成gray碼56置換(polya)56字典序全排

2、列57字典序組合572.12.22.32.42.52.6第 3 頁(yè)ACM 集訓(xùn)資料by colin3、結(jié)構(gòu)58并查集58堆59線段樹60子段和65子陣和653.13.23.33.43.5第 4 頁(yè)ACM 集訓(xùn)資料by colin4、數(shù)論66階乘最后非 0 位66模線性方程組67素?cái)?shù)68歐拉函數(shù)694.14.24.34.4第 5 頁(yè)ACM 集訓(xùn)資料by colin5、數(shù)值計(jì)算705.15.25.3定計(jì)算(Romberg)70多項(xiàng)式求根(牛頓法)72周期性方程(追趕法)73第 6 頁(yè)ACM 集訓(xùn)資料by colin6、圖論NP搜索74最大團(tuán)74最大團(tuán)(n<64)(faster)756.16.

3、2第 7 頁(yè)ACM 集訓(xùn)資料by colin7、圖論連通性77無(wú)向圖關(guān)鍵點(diǎn)(dfs鄰接陣)77無(wú)向圖關(guān)鍵邊(dfs鄰接陣)78無(wú)向圖的塊(bfs鄰接陣)79無(wú)向圖連通分支(dfs/bfs鄰接陣)80有向圖強(qiáng)連通分支(dfs/bfs鄰接陣)81有向圖最小點(diǎn)基(鄰接陣)827.17.27.37.47.57.6第 8 頁(yè)ACM 集訓(xùn)資料by colin8、圖論匹配83二分圖最大匹配(hungary鄰接表)83二分圖最大匹配(hungary鄰接陣)84二分圖最大匹配(hungary正向表)848.18.28.38.4 二分圖最佳匹配(kuhn_munkras鄰接陣)858.58.68.7一般圖匹配(鄰

4、接表)86一般圖匹配(鄰接陣)87一般圖匹配(正向表)87第 9 頁(yè)ACM 集訓(xùn)資料by colin9、圖論網(wǎng)絡(luò)流88最大流(鄰接陣)88上下界最大流(鄰接陣)89上下界最小流(鄰接陣)90最大流無(wú)流量(鄰接陣)91最小費(fèi)用最大流(鄰接陣)919.19.29.39.49.5第 10 頁(yè)ACM 集訓(xùn)資料by colin10、圖論應(yīng)用92第 11 頁(yè)ACM 集訓(xùn)資料by colin10.1歐拉回路(鄰接陣)92第 12 頁(yè)ACM 集訓(xùn)資料by colin10.2樹的前序表轉(zhuǎn)化93第 13 頁(yè)ACM 集訓(xùn)資料by colin10.3樹的優(yōu)化算法94第 14 頁(yè)ACM 集訓(xùn)資料by colin10.4

5、拓?fù)渑判?鄰接陣)95第 15 頁(yè)ACM 集訓(xùn)資料by colin10.5最佳邊割集96第 16 頁(yè)ACM 集訓(xùn)資料by colin10.6最佳點(diǎn)割集97第 17 頁(yè)ACM 集訓(xùn)資料by colin10.7最小邊割集98第 18 頁(yè)ACM 集訓(xùn)資料by colin10.8最小點(diǎn)割集99第 19 頁(yè)ACM 集訓(xùn)資料by colin10.9最小路徑覆蓋101第 20 頁(yè)ACM 集訓(xùn)資料by colin11、圖論支撐樹101最小生成樹(kruskal鄰接表)101最小生成樹(kruskal正向表)103最小生成樹(prim+binary_heap鄰接表)104最小生成樹(prim+binary_he

6、ap正向表)105最小生成樹(prim+mapped_heap鄰接表)106最小生成樹(prim+mapped_heap正向表)108最小生成樹(prim鄰接陣)109最小樹形圖(鄰接陣)10911.111.211.311.411.511.611.711.8第 21 頁(yè)ACM 集訓(xùn)資料by colin12、12.112.212.312.412.512.612.712.812.9圖論最短路徑111最短路徑(單源bellman_ford鄰接陣)111最短路徑(單源dijkstra+bfs鄰接表)111最短路徑(單源dijkstra+bfs正向表)112最短路徑(單源dijkstra+binary_

7、heap鄰接表)113最短路徑(單源dijkstra+binary_heap正向表)114最短路徑(單源dijkstra+mapped_heap鄰接表)115最短路徑(單源dijkstra+mapped_heap正向表)116最短路徑(單源dijkstra鄰接陣)117最短路徑(多源floyd_warshall鄰接陣)118第 22 頁(yè)ACM 集訓(xùn)資料by colin13、應(yīng)用11813.1 Joseph問題11813.2 N皇后構(gòu)造解11913.313.413.513.613.713.813.9布爾母函數(shù)120第k元素120幻方構(gòu)造121模式匹配(kmp)122逆序?qū)?shù)123字符串最小表示1

8、23最長(zhǎng)公共單調(diào)子序列12413.10 最長(zhǎng)子序列12513.11 最大子串匹配12613.1213.13最大子段和127最大子陣和127第 23 頁(yè)ACM 集訓(xùn)資料by colin14、14.114.214.314.414.514.6其它128大數(shù)(只能處理正數(shù))128分?jǐn)?shù)134矩陣136線性方程組138線性相關(guān)140日期140第 24 頁(yè)ACM 集訓(xùn)資料by colin1、幾何1.1注意1.注意舍入方式(0.5 的舍入方向);防止輸出-0.2.幾何題注意多測(cè)試不對(duì)稱數(shù)據(jù).3.整數(shù)幾何注意 xmult 和 dmult 是否會(huì)出界;符點(diǎn)幾何注意 eps 的使用.4.避免使用斜率;注意除數(shù)是否會(huì)

9、為 0.5.公式一定要化簡(jiǎn)后再代入.6.同一個(gè) 2*PI 域內(nèi)兩角度差應(yīng)該是abs(a1-a2)<beta|abs(a1-a2)>pi+pi-beta; 相等應(yīng)該是abs(a1-a2)<eps|abs(a1-a2)>pi+pi-eps;7.需要的話盡量使用 atan2,注意:atan2(0,0)=0,atan2(1,0)=pi/2,atan2(-1,0)=-pi/2,atan2(0,1)=0,atan2(0,-1)=pi.8. cross product = |u|*|v|*sin(a)dot product = |u|*|v|*cos(a)9. (P1-P0)x(P2

10、-P0)結(jié)果的意義:正: <P0,P1>在<P0,P2>順時(shí)針(0,pi)內(nèi)負(fù): <P0,P1>在<P0,P2>逆時(shí)針(0,pi)內(nèi)0 : <P0,P1>,<P0,P2>共線,夾角為 0 或 pi10. 誤差限缺省使用 1e-8!1.2幾何公式三角形:1.2.3.4.5.半周長(zhǎng) P=(a+b+c)/2面積 S=aHa/2=absin(C)/2=sqrt(P(P-a)(P-b)(P-c)中線 Ma=sqrt(2(b2+c2)-a2)/2=sqrt(b2+c2+2bccos(A)/2 角平分線 Ta=sqrt(bc(b+c)2

11、-a2)/(b+c)=2bccos(A/2)/(b+c) 高線 Ha=bsin(C)=csin(B)=sqrt(b2-(a2+b2-c2)/(2a)2)第 25 頁(yè)ACM 集訓(xùn)資料by colin6. 內(nèi)切圓半徑 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)四邊形:D1,D2 為對(duì)角線,M 對(duì)角線中點(diǎn)連線,A 為對(duì)角

12、線夾角1. a2+b2+c2+d2=D12+D22+4M22. S=D1D2sin(A)/2(以下對(duì)圓的內(nèi)接四邊形)3. ac+bd=D1D24. S=sqrt(P-a)(P-b)(P-c)(P-d),P 為半周長(zhǎng)正 n 邊形:R 為外接圓半徑,r 為內(nèi)切圓半徑1.2.3.4.中心角 A=2PI/n內(nèi)角邊長(zhǎng)面積C=(n-2)PI/na=2sqrt(R2-r2)=2Rsin(A/2)=2rtan(A/2) S=nar/2=nr2tan(A/2)=nR2sin(A)/2=na2/(4tan(A/2)圓:1.2.3.4.5.弧長(zhǎng)弦長(zhǎng)l=rAa=2sqrt(2hr-h2)=2rsin(A/2)弓形高

13、h=r-sqrt(r2-a2/4)=r(1-cos(A/2)=atan(A/4)/2扇形面積 S1=rl/2=r2A/2弓形面積 S2=(rl-a(r-h)/2=r2(A-sin(A)/2棱柱:1.2.3.體積 V=Ah,A 為底面積,h 為高側(cè)面積 S=lp,l 為棱長(zhǎng),p 為直截面周長(zhǎng)全面積 T=S+2A棱錐:1. 體積 V=Ah/3,A 為底面積,h 為高(以下對(duì)正棱錐)2. 側(cè)面積 S=lp/2,l 為斜高,p 為底面周長(zhǎng)3. 全面積 T=S+A棱臺(tái):1. 體積 V=(A1+A2+sqrt(A1A2)h/3,A1.A2 為上下底面積,h 為高(以下為正棱臺(tái))2.3.側(cè)面積 S=(p1+

14、p2)l/2,p1.p2 為上下底面周長(zhǎng),l 為斜高全面積 T=S+A1+A2第 26 頁(yè)ACM 集訓(xùn)資料by colin圓柱:1.2.3.側(cè)面積 S=2PIrh全面積 T=2PIr(h+r)體積V=PIr2h圓錐:1.2.3.4.母線l=sqrt(h2+r2)側(cè)面積 S=PIrl全面積 T=PIr(l+r)體積 V=PIr2h/3圓臺(tái):1.2.3.4.母線 l=sqrt(h2+(r1-r2)2)側(cè)面積 S=PI(r1+r2)l全面積 T=PIr1(l+r1)+PIr2(l+r2)體積 V=PI(r12+r22+r1r2)h/3球:1. 全面積 T=4PIr22. 體積 V=4PIr3/3球臺(tái)

15、:1.2.3.側(cè)面積 S=2PIrh全面積 T=PI(2rh+r12+r22)體積 V=PIh(3(r12+r22)+h2)/6球扇形:1.2.全面積 T=PIr(2h+r0),h 為球冠高,r0 為球冠底面半徑體積 V=2PIr2h/31.3多邊形#include <stdlib.h> #include <math.h> #define MAXN 1000#define offset 10000 #define eps 1e-8#define zero(x) (x)>0?(x):-(x)<eps)#define _sign(x) (x)>eps?1:

16、(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);第 27 頁(yè)ACM 集訓(xùn)資料by colin/判定凸多邊形,頂點(diǎn)按順時(shí)針或逆時(shí)針給出, int is_convex(int n,point* p)int i,s3=1,1,1;for (i=0;i<n&&s1|s2;i+) s_sign(xmult(p(i+1)%n

17、,p(i+2)%n,pi)=0;return s1|s2;相鄰邊共線/判定凸多邊形,頂點(diǎn)按順時(shí)針或逆時(shí)針給出,不int is_convex_v2(int n,point* p)int i,s3=1,1,1;for (i=0;i<n&&s0&&s1|s2;i+)相鄰邊共線s_sign(xmult(p(i+1)%n,p(i+2)%n,pi)=0;return s0&&s1|s2;/判點(diǎn)在凸多邊形內(nèi)或多邊形邊上,頂點(diǎn)按順時(shí)針或逆時(shí)針給出int inside_convex(point q,int n,point* p)int i,s3=1,1,1;

18、for (i=0;i<n&&s1|s2;i+) s_sign(xmult(p(i+1)%n,q,pi)=0;return s1|s2;/判點(diǎn)在凸多邊形內(nèi),頂點(diǎn)按順時(shí)針或逆時(shí)針給出,在多邊形邊上返回 0 int inside_convex_v2(point q,int n,point* p)int i,s3=1,1,1;for (i=0;i<n&&s0&&s1|s2;i+) s_sign(xmult(p(i+1)%n,q,pi)=0;return s0&&s1|s2;/判點(diǎn)在任意多邊形內(nèi),頂點(diǎn)按順時(shí)針或逆時(shí)針給出/on_

19、edge 表示點(diǎn)在多邊形邊上時(shí)的返回值,offset 為多邊形坐標(biāo)上限int inside_polygon(point q,int n,point* p,int on_edge=1) point q2;int i=0,count; while (i<n)for (count=i=0,q2.x=rand()+offset,q2.y=rand()+offset;i<n;i+) if(zero(xmult(q,pi,p(i+1)%n)&&(pi.x-q.x)*(p(i+1)%n.x-q.x)<eps&&(pi.y-q.y)*(p(i+1)%n.y-q

20、.y)<eps)第 28 頁(yè)ACM 集訓(xùn)資料by colinreturn on_edge; else if (zero(xmult(break;else2,pi)if(xmult(q,pi,q2)*xmult(q,p(i+1)%n,q2)<-eps&&xmult(pi,q,p(i+1)%n)*xmult(pi,q2,p(i+1)%n)<-eps)count+; return count&1;inline int opposite_side(point p1,point p2,point l1,point l2) return xmult(l1,p1,l

21、2)*xmult(l1,p2,l2)<-eps;inline int dot_online_in(point p,point l1,point l2)return zero(xmult(p,l1,l2)&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;/判線段在任意多邊形內(nèi),頂點(diǎn)按順時(shí)針或逆時(shí)針給出,與邊界相交返回 1 int inside_polygon(point l1,point l2,int n,point* p)point tMAXN,tt; int i,j,k=0;if (

22、!inside_polygon(l1,n,p)|!inside_polygon(l2,n,p) return 0;for (i=0;i<n;i+)if (opposite_side(l1,l2,pi,p(i+1)%n)&&opposite_side(pi,p(i+1)%n,l1,l2) return 0;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

23、(i=0;i<k;i+)for (j=i+1;j<k;j+) tt.x=(ti.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)第 29 頁(yè)ACM 集訓(xùn)資料by colinpoint 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.

24、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 t1=0,t2; i

25、nt i; ret.x=ret.y=0;for (i=1;i<n-1;i+)if (fabs(t2=xmult(p0,pi,pi+1)>eps)t=barycenter(p0,pi,pi+1); ret.x+=t.x*t2;ret.y+=t.y*t2; t1+=t2;if (fabs(t1)>eps)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)第 30 頁(yè)ACM 集訓(xùn)

26、資料by colinstruct pointdouble x,y;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);int same_side(point p1,point p2,point l1,point l2) return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;point intersection(point u1,point u2,point v1,point v2) point ret=u1;double

27、 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 側(cè)切割,保證 l1,l2,side 不共線void polygon_cut(int& n,point* p,point l1,point l2,point side) point pp100;int m=0,i;for (i=0;i

28、<n;i+)if (same_side(pi,side,l1,l2) ppm+=pi;if (!same_side(pi,p(i+1)%n,l1,l2)&&!(zero(xmult(pi,l1,l2)&&zero(xmult(p(i+1)%n,l1,l2)ppm+=intersection(pi,p(i+1)%n,l1,l2);for (n=i=0;i<m;i+)if (!i|!zero(ppi.x-ppi-1.x)|!zero(ppi.y-ppi-1.y) pn+=ppi;if (zero(pn-1.x-p0.x)&&zero(pn

29、-1.y-p0.y) n-;if (n<3)n=0;1.5浮點(diǎn)函數(shù)/浮點(diǎn)幾何函數(shù)庫(kù)#include <math.h>#define eps 1e-8第 31 頁(yè)ACM 集訓(xùn)資料by colin#define zero(x) (x)>0?(x):-(x)<eps) struct pointdouble x,y;struct linepoint a,b;/計(jì)算 cross product (P1-P0)x(P2-P0) double xmult(point p1,point p2,point p0)return (p1.x-p0.x)*(p2.y-p0.y)-(p2.

30、x-p0.x)*(p1.y-p0.y);double xmuouble x1,double y1,double x2,double y2,double x0,double y0)return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);/計(jì)算dot product (P1-P0).(P2-P0) double dmult(point p1,point p2,point p0)return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);double dmuouble x1,double y1,double x2,double

31、y2,double x0,double y0)return (x1-x0)*(x2-x0)+(y1-y0)*(y2-y0);/兩點(diǎn)距離double distance(point p1,point p2)return sqrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);double distance(double x1,double y1,double x2,double y2) return sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);/判三點(diǎn)共線int dots_inline(point p1,point p2,

32、point p3) return zero(xmult(p1,p2,p3);int dots_inline(double x1,double y1,double x2,double y2,double x3,double y3) return zero(xmult(x1,y1,x2,y2,x3,y3);/判點(diǎn)是否段上,包括端點(diǎn)int dot_online_in(point p,line l)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)&l

33、t;eps;int dot_online_in(point p,point l1,point l2)return zero(xmult(p,l1,l2)&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;int dot_online_in(double x,double y,double x1,double y1,double x2,double y2)第 32 頁(yè)ACM 集訓(xùn)資料by colinreturn zero(xmult(x,y,x1,y1,x2,y2)&&(x1-x

34、)*(x2-x)<eps&&(y1-y)*(y2-y)<eps;/判點(diǎn)是否段上,不包括端點(diǎn)int dot_online_ex(point p,line l) returndot_online_in(p,l)&&(!zero(p.x-l.a.x)|!zero(p.y-l.a.y)&&(!zero(p.x-l.b.x)|!zero(p.y-l.b.y);int dot_online_ex(point p,point l1,point l2) returndot_online_in(p,l1,l2)&&(!zero(p.x-

35、l1.x)|!zero(p.y-l1.y)&&(!zero(p.x-l2.x)|!zero(p.y-l2.y);int dot_online_ex(double x,double y,double x1,double y1,double x2,double y2) returndot_online_in(x,y,x1,y1,x2,y2)&&(!zero(x-x1)|!zero(y-y1)&&(!zero(x-x2)|!zero(y-y2);/判兩點(diǎn)段同側(cè),點(diǎn)段上返回 0int same_side(point p1,point p2,line l)

36、return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>eps;int same_side(point p1,point p2,point l1,point l2) return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;/判兩點(diǎn)段異側(cè),點(diǎn)段上返回 0int opposite_side(point p1,point p2,line l)return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)<-eps;int opposite_side(point p1,point p2,point l1

37、,point l2) return xmult(l1,p1,l2)*xmult(l1,p2,l2)<-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 u1,point u2,point v1,point v2)return zero(u1.x-u2.x)*(v1.y-v2.y)-(v1.x-v2.x)*(u1.y-u2.y);/判兩直線垂直int perpendicular(line u,l

38、ine 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);第 33 頁(yè)ACM 集訓(xùn)資料by colinint perpendicular(point u1,point u2,point v1,point v2)return zero(u1.x-u2.x)*(v1.x-v2.x)+(u1.y-u2.y)*(v1.y-v2.y);/判兩線段相交,包括端點(diǎn)和部分重合int intersect_in(line u,line v)if (!dots_inline(u.a,u.b,v.a)|!dots_inline(u

39、.a,u.b,v.b) return !same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u);return dot_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 u1,point u2,point v1,point v2) if (!dots_inline(u1,u2,v1)|!dots_inline(u1,u2,v2)return !same_side(u1,u2,v1,v2)&

40、;&!same_side(v1,v2,u1,u2); returndot_online_in(u1,v1,v2)|dot_online_in(u2,v1,v2)|dot_online_in(v1,u1,u2)|dot_online_in(v2,u1,u 2);/判兩線段相交,不包括端點(diǎn)和部分重合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 u1,point u2,point v1,point v

41、2)return opposite_side(u1,u2,v1,v2)&&opposite_side(v1,v2,u1,u2);/計(jì)算兩直線交點(diǎn),注意事先直線是否平行!/線段交點(diǎn)請(qǐng)另外判線段相交(同時(shí)還是要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-

42、u.a.x)*t;ret.y+=(u.b.y-u.a.y)*t;return ret;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;第 34 頁(yè)ACM 集訓(xùn)資料by colin/點(diǎn)到直線上的

43、最近點(diǎn)point ptoline(point p,line l)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 ptoline(point p,point l1,point l2) point t=p;t.x+=l1.y-l2.y,t.y+=l2.x-l1.x; return intersection(p,t,l1,l2);/點(diǎn)到直線距離double disptoline(point p,line l)return fabs(xmult(p,l.a,l.b)/distance

44、(l.a,l.b);double disptoline(point p,point l1,point l2) return fabs(xmult(p,l1,l2)/distance(l1,l2);double disptoline(double x,double y,double x1,double y1,double x2,double y2) return fabs(xmult(x,y,x1,y1,x2,y2)/distance(x1,y1,x2,y2);/點(diǎn)到線段上的最近點(diǎn)point ptoseg(point p,line l)point t=p;t.x+=l.a.y-l.b.y,t.y

45、+=l.b.x-l.a.x;if (xmult(l.a,t,p)*xmult(l.b,t,p)>eps)return distance(p,l.a)<distance(p,l.b)?l.a:l.b; return intersection(p,t,l.a,l.b);point ptoseg(point p,point l1,point l2) point t=p;t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;if (xmult(l1,t,p)*xmult(l2,t,p)>eps)return distance(p,l1)<distance(p,l2)?l1

46、:l2; return intersection(p,t,l1,l2);/點(diǎn)到線段距離double disptoseg(point p,line l) point t=p;第 35 頁(yè)ACM 集訓(xùn)資料by colint.x+=l.a.y-l.b.y,t.y+=l.b.x-l.a.x;if (xmult(l.a,t,p)*xmult(l.b,t,p)>eps)return distance(p,l.a)<distance(p,l.b)?distance(p,l.a):distance(p,l.b); return fabs(xmult(p,l.a,l.b)/distance(l.a,

47、l.b);double disptoseg(point p,point l1,point l2) point t=p;t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;if (xmult(l1,t,p)*xmult(l2,t,p)>eps)return distance(p,l1)<distance(p,l2)?distance(p,l1):distance(p,l2); return fabs(xmult(p,l1,l2)/distance(l1,l2);/矢量 V 以 P 為頂點(diǎn)逆時(shí)針旋轉(zhuǎn) angle 并放大 scale 倍point rotate(point v,p

48、oint 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 <math.h>struct pointdouble x,y;/計(jì)算 cross product (P1-P0)x(P2-P0) double xmult(point p1,point p2,point p0)return

49、(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);double xmuouble x1,double y1,double x2,double y2,double x0,double y0)return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);/計(jì)算三角形面積,輸入三頂點(diǎn)double area_triangle(point p1,point p2,point p3) return fabs(xmult(p1,p2,p3)/2;double area_triangle(double x1,double y1,double x2,

50、double y2,double x3,double y3) return fabs(xmult(x1,y1,x2,y2,x3,y3)/2;第 36 頁(yè)ACM 集訓(xùn)資料by colin/計(jì)算三角形面積,輸入三邊長(zhǎng)double area_triangle(double a,double b,double c) double s=(a+b+c)/2;return sqrt(s*(s-a)*(s-b)*(s-c);/計(jì)算多邊形面積,頂點(diǎn)按順時(shí)針或逆時(shí)針給出double area_polygon(int n,point* p)double s1=0,s2=0; int i;for (i=0;i<

51、n;i+) s1+=p(i+1)%n.y*pi.x,s2+=p(i+1)%n.y*p(i+2)%n.x;return fabs(s1-s2)/2;1.7球面#include <math.h>const double pi=acos(-1);/計(jì)算圓心角lat 表示緯度,-90<=w<=90,lng 表示經(jīng)度/返回兩點(diǎn)所在大圓劣弧對(duì)應(yīng)圓心角,0<=angle<=pidouble angle(double lng1,double lat1,double lng2,double lat2) double dlng=fabs(lng1-lng2)*pi/180;wh

52、ile (dlng>=pi+pi) dlng-=pi+pi;if (dlng>pi)dlng=pi+pi-dlng; lat1*=pi/180,lat2*=pi/180;return acos(cos(lat1)*cos(lat2)*cos(dlng)+sin(lat1)*sin(lat2);/計(jì)算距離,r 為球半徑double line_dist(double r,double lng1,double lat1,double lng2,double lat2) double dlng=fabs(lng1-lng2)*pi/180;while (dlng>=pi+pi) dl

53、ng-=pi+pi;if (dlng>pi)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);第 37 頁(yè)ACM 集訓(xùn)資料by colin/計(jì)算球面距離,r 為球半徑inline double sphere_dist(double r,double lng1,double lat1,double lng2,double lat2) return r*angle(lng1,lat1,lng2,lat2);1.8三角形#include <math.h>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