1、1 .計(jì)算幾何1.1注意1 .注意舍入方式(0.5 的舍入方向)；防止輸出-0.2 .幾何題注意多測試不對稱數(shù)據(jù).3 .整數(shù)幾何注意 xmult 和 dmult 是否會出界；符點(diǎn)幾何注意 eps 的使用.4 .避免使用斜率；注意除數(shù)是否會為 0.5 .公式一定要化簡后再代入.6 .判斷同一個 2*PI 域內(nèi)兩角度差應(yīng)該是abs(a1-a2)pi+pi-beta;相等應(yīng)該是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)=

2、pi.8 .crossproduct=|u|*|v|*sin(a)dotproduct=|u|*|v|*cos(a)9 .(P1-P0)x(P2-P0)結(jié)果的意義：正：在順時針(0,pi)內(nèi)負(fù)：在逆時針(0,pi)內(nèi)0:,共線,夾角為 0 或 pi10 .誤差限缺省使用 1e-8!11 2 幾何公式三角形：1 .半周長 P=(a+b+c)/22 .面積 S=aHa/2=absin(C)/2=sqrt(P(P-a)(P-b)(P-c)3 .中線 Ma=sqrt(2(bA2+cA2)-aA2)/2=sqrt(bA2+cA2+2bccos(A)/24 .角平分線 Ta=sqrt(bc(b+c)A2-

3、aA2)/(b+c)=2bccos(A/2)/(b+c)5 .高線 Ha=bsin(C)=csin(B)=sqrt(bA2-(aA2+bA2-cA2)/(2a)A2)6 .內(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 為對角線，M 對角線中點(diǎn)連線，A 為對角線夾角1 aA2+bA2+cA2

4、+dA2=D1A2+D2A2+4MA22S=D1D2sin(A)/2(以下對圓的內(nèi)接四邊形)3ac+bd=D1D24S=sqrt(P-a)(P-b)(P-c)(P-d),P 為半周長正 n 邊形：R 為外接圓半徑,r 為內(nèi)切圓半徑1 .中心角 A=2PI/n2 .內(nèi)角 C=(n-2)PI/n3 .邊長 a=2sqrt(RA2-rA2)=2Rsin(A/2)=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

5、-sqrt(rA2-aA2/4)=r(1-cos(A/2)=atan(A/4)/24 .扇形面積 S1=rl/2=rA2A/25 .弓形面積 S2=(rl-a(r-h)/2=rA2(A-sin(A)/2棱柱：1 .體積 V=Ah,A 為底面積,h 為高2 .側(cè)面積 S=lp,l 為棱長,p 為直截面周長3 .全面積 T=S+2A棱錐：1 .體積 V=Ah/3,A 為底面積,h 為高(以下對正棱錐)2 .側(cè)面積 S=lp/2,l 為斜高,p 為底面周長3 .全面積 T=S+A棱臺：1.%2.體積 V=(A1+A2+sqrt(A1A2)h/3,A1.A2 為上下底面積，h 為高(以下為正棱臺)2.

6、%2.側(cè)面積 S=(p1+p2)l/2,p1.p2 為上下底面周長,l 為斜高3.%2.全面積 T=S+A1+A2圓柱：1 .側(cè)面積 S=2PIrh2 .全面積 T=2PIr(h+r)3 .體積 V=PM2h圓錐：6.%2.母線 l=sqrt(hA2+rA2)7.%2.側(cè)面積 S=PIrl8.%2.全面積 T=PIr(l+r)9.%2.體積 V=PM2h/3圓臺：.母線 l=sqrt(hA2+(r1-r2)A2).側(cè)面積 S=PI(r1+r2)l.全面積 T=PIr1(l+r1)+PIr2(l+r2).體積 V=PI(r1A2+r2A2+nr2)h/3球：.全面積 T=4PIrA2.體積 V=

7、4PM3/3球臺：.側(cè)面積 S=2PIrh.全面積 T=PI(2rh+r1A2+r2A2)3.體積 V=PIh(3(r1A2+r2A2)+八人 2)/6球扇形:面積 T=PIr（2h+r0）,h 為球冠高,r0 為球冠底面半徑積 V=2PM2h/3Euler 的任意四面體體積公式（已知邊長求體積）多邊形#include#include#defineMAXN1000#defineoffset10000#defineeps1e-8#definezero(x)(x)0?(x):-(x)eps?1:(x)-eps?2:0)structpointdoublex,y;structlinepointa,b;

8、doublexmult(pointp1,pointp2,pointp0)return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);)36V22P222pq-n2222pr-m2222pq-n22q222qr-12222pr-m2222qr-12(x1,y1,z1),(x2,y2,z2),(x3,y3,z3)V=6(x4,y4,z4)1111x1x2x3x4.y1y2y3y4z1z2z3z4已知 4 點(diǎn)坐標(biāo)求體積（其中四個點(diǎn)的坐標(biāo)分別為/判定凸多邊形，頂點(diǎn)按順時針或逆時針給出，允許相鄰邊共線intis_convex(intn,point*p)in

9、t 閭 3=1,1,1;for(i=0;in&s1|s2;i+)s_sign(xmult(p(i+1)%n,p(i+2)%n,pi)=0;returns1|s2;/判定凸多邊形，頂點(diǎn)按順時針或逆時針給出，不允許相鄰邊共線intis_convex_v2(intn,point*p)inti,s3=1,1,1;for(i=0;in&s0&s1|s2;i+)s_sign(xmult(p(i+1)%n,p(i+2)%n,pi)=0;returns0&s1|s2;/判點(diǎn)在凸多邊形內(nèi)或多邊形邊上，頂點(diǎn)按順時針或逆時針給出intinside_convex(pointq,intn,point*p)inti,s3

10、=1,1,1;for(i=0;in&s1|s2;i+)s_sign(xmult(p(i+1)%n,q,pi)=0;returns1|s2;/判點(diǎn)在凸多邊形內(nèi)，頂點(diǎn)按順時針或逆時針給出，在多邊形邊上返回0intinside_convex_v2(pointq,intn,point*p)inti,s3=1,1,1;for(i=0;in&s0&s1|s2;i+)s_sign(xmult(p(i+1)%n,q,pi)=0;returns0&s1|s2;/判點(diǎn)在任意多邊形內(nèi)，頂點(diǎn)按順時針或逆時針給出/on_edge 表示點(diǎn)在多邊形邊上時的返回值,offset 為多邊形坐標(biāo)上限intinside_polyg

11、on(pointq,intn,point*p,inton_edge=1)pointq2;inti=0,count;while(in)for(count=i=0,q2.x=rand()+offset,q2.y=rand()+offset;in;i+)if億ero(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.y)eps)returnon_edge;elseif 億 ero(xmult(q,q2,pi)break;elseif(xmult(q,pi,q2)*xmult(q,p(i+1)%n,

12、q2)-eps&xmult(pi,q,p(i+1)%n)*xmult(pi,q2,p(i+1)%n)-eps)count+;returncount&1;inlineintopposite_side(pointp1,pointp2,pointl1,pointl2)returnxmult(l1,p1,l2)*xmult(l1,p2,l2)-eps;inlineintdot_online_in(pointp,pointl1,pointl2)returnzero(xmult(p,l1,l2)&(l1.x-p.x)*(l2.x-p.x)eps&(l1.y-p.y)*(l2.y-p.y)eps;/判線段在

13、任意多邊形內(nèi)，頂點(diǎn)按順時針或逆時針給出，與邊界相交返回 1intinside_polygon(pointl1,pointl2,intn,point*p)pointtMAXN,tt;inti,j,k=0;if(!inside_polygon(l1,n,p)|!inside_polygon(l2,n,p)return0;for(i=0;in;i+)if(opposite_side(l1,l2,pi,p(i+1)%n)&opposite_side(pi,p(i+1)%n,l1,l2)return0;elseif(dot_online_in(l1,pi,p(i+1)%n)tk+=l1;elseif(d

14、ot_online_in(l2,pi,p(i+1)%n)tk+=l2;elseif(dot_online_in(pi,l1,l2)tk+=pi;for(i=0;ik;i+)for(j=i+1;jk;j+)tt.x=(ti.x+tj.x)/2;tt.y=(ti.y+tj.y)/2;if(!inside_polygon(tt,n,p)return0;return1;pointintersection(lineu,linev)pointret=u.a;doublet=(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.

15、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;returnret;pointbarycenter(pointa,pointb,pointc)lineu,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;returnintersection(u,v);/多邊形重心pointbarycenter(intn,point*p)pointret,t;

16、doublet1=0,t2;inti;ret.x=ret.y=0;for(i=1;ieps)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;returnret;)多邊形切割/多邊形切割/可用于半平面交#defineMAXN100#defineeps1e-8#definezero(x)(x)0?(x):-(x)eps;pointintersection(pointu1,pointu2,pointv1,pointv2)pointret=u1;doublet

17、=(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;returnret;將多邊形沿 l1,l2 確定的直線切割在 side 側(cè)切割，保證 l1,l2,side 不共線voidpolygon_cut(int&n,point*p,pointl1,pointl2,pointside)pointppMAXN;intm=0,i;for(i=0;in;i+)if(same_side(

18、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;im;i+)if(!i|!zero(ppi.x-ppi-1.x)|!zero(ppi.y-ppi-1.y)pn+=ppi;if 億 ero(pn-1.x-p0.x)&zero(pn-1.y-p0.y)n-;if(n3)n=0;浮點(diǎn)函數(shù)/浮點(diǎn)幾何函數(shù)庫#include#defineeps1e-8#d

19、efinezero(x)(x)0?(x):-(x)eps)structpointdoublex,y;structlinepointa,b;計(jì)算 crossproduct(P1-P0)x(P2-P0)doublexmult(pointp1,pointp2,pointp0)return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);doublexmult(doublex1,doubley1,doublex2,doubley2,doublex0,doubley0)return(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);/計(jì)算 dot

20、product(P1-P0).(P2-P0)doubledmult(pointp1,pointp2,pointp0)return(p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);doubledmult(doublex1,doubley1,doublex2,doubley2,doublex0,doubley0)return(x1-x0)*(x2-x0)+(y1-y0)*(y2-y0);/兩點(diǎn)距離doubledistance(pointp1,pointp2)returnsqrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p

21、1.y-p2.y);doubledistance(doublex1,doubley1,doublex2,doubley2)returnsqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);/判三點(diǎn)共線intdots_inline(pointp1,pointp2,pointp3)returnzero(xmult(p1,p2,p3);intdots_inline(doublex1,doubley1,doublex2,doubley2,doublex3,doubley3)returnzero(xmult(x1,y1,x2,y2,x3,y3);/判點(diǎn)是否在線段上，包括端點(diǎn)intdot

22、_online_in(pointp,linel)returnzero(xmult(p,l.a,l.b)&(lax-p.x)*(l.b.x-p.x)eps&(lay-p.y)*(l.b.y-p.y)eps;intdot_online_in(pointp,pointl1,pointl2)returnzero(xmult(p,l1,l2)&(l1.x-p.x)*(l2.x-p.x)eps&(l1.y-p.y)*(l2.y-p.y)eps;)intdot_online_in(doublex,doubley,doublex1,doubley1,doublex2,doubley2)returnzero(x

23、mult(x,y,x1,y1,x2,y2)&(x1-x)*(x2-x)eps&(y1-y)*(y2-y)eps;)intsame_side(pointp1,pointp2,pointl1,pointl2)returnxmult(l1,p1,l2)*xmult(l1,p2,l2)eps;)/判兩點(diǎn)在線段異側(cè)，點(diǎn)在線段上返回 0intopposite_side(pointp1,pointp2,linel)returnxmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)-eps;)intopposite_side(pointp1,pointp2,pointl1,pointl2)re

24、turnxmult(l1,p1,l2)*xmult(l1,p2,l2)eps)returndistance(p,l.a)eps)returndistance(p,l1)eps)returndistance(p,l.a)eps)returndistance(p,l1)distance(p,l2)?distance(p,l1):distance(p,l2);returnfabs(xmult(p,l1,l2)/distance(l1,l2);/矢量 V 以 P 為頂點(diǎn)逆時針旋轉(zhuǎn) angle 并放大 scale 倍pointrotate(pointv,pointp,doubleangle,double

25、scale)pointret=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;returnret;/p 點(diǎn)關(guān)于直線 L 的對稱點(diǎn)ponitsymmetricalPointofLine(pointp,lineL)pointp2;doubled;d=L.a*L.a+L.b*L.b;p2.x=(L.b*L.b*p.x-L.a*L.a*p.x-2*L.a*L.b*p.y-2*L.a*L.c)/d;p2.y=(L.a*L.a*p.y-L.

26、b*L.b*p.y-2*L.a*L.b*p.x-2*L.b*L.c)/d;returnp2;/求兩點(diǎn)的平分線linebisector(point&a,point&b)lineab,ans;ab.set(a,b);doublemidx=(a.x+b.x)/2.0,midy=(a.y+b.y)/2.0;ans.a=-ab.b,ans.b=-ab.a,ans.c=-ab.b*midx+ab.a*midy;returnans;)/已知入射線、鏡面，求反射線。/a1,b1,c1 為鏡面直線方程(a1x+b1y+c1=0,下同)系數(shù)；a2,b2,c2 為入射光直線方程系數(shù)；a,b,c 為反射光直線方程系數(shù)

27、./光是有方向的，使用時注意：入射光向量：;反射光向量：./不要忘記結(jié)果中可能會有negativezerosvoidreflect(doublea1,doubleb1,doublec1,doublea2,doubleb2,doublec2,double&a,double&b,double&c)doublen,m;doubletpb,tpa;tpb=b1*b2+a1*a2;tpa=a2*b1-a1*b2;m=(tpb*b1+tpa*a1)/(b1*b1+a1*a1);n=(tpa*b1-tpb*a1)/(b1*b1+a1*a1);if(fabs(a1*b2-a2*b1)1e-20)a=a2;b=

28、b2;c=c2;return;)doublexx,yy;/(xx,yy)是入射線與鏡面的交點(diǎn)。xx=(b1*c2-b2*c1)/(a1*b2-a2*b1);yy=(a2*c1-a1*c2)/(a1*b2-a2*b1);a=n;b=-m;c=m*yy-xx*n;)面積#includestructpointdoublex,y;計(jì)算 crossproduct(P1-P0)x(P2-P0)doublexmult(pointp1,pointp2,pointp0)return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);)doublexmult(doubl

29、ex1,doubley1,doublex2,doubley2,doublex0,doubley0)return(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);)計(jì)算三角形面積，輸入三頂點(diǎn)doublearea_triangle(pointp1,pointp2,pointp3)returnfabs(xmult(p1,p2,p3)/2;)doublearea_triangle(doublex1,doubley1,doublex2,doubley2,doublex3,doubley3)returnfabs(xmult(x1,y1,x2,y2,x3,y3)/2;)計(jì)算三角形面積，輸入三邊

30、長doublearea_triangle(doublea,doubleb,doublec)doubles=(a+b+c)/2;returnsqrt(s*(s-a)*(s-b)*(s-c);)/計(jì)算多邊形面積，頂點(diǎn)按順時針或逆時針給出doublearea_polygon(intn,point*p)doubles1=0,s2=0;inti;for(i=0;in;i+)s1+=p(i+1)%n.y*pi.x,s2+=p(i+1)%n.y*p(i+2)%n.x;returnfabs(s1-s2)/2;)球面#includeconstdoublepi=acos(-1);/計(jì)算圓心角 lat 表示緯度，-

31、90=w=90,lng 表示經(jīng)度/返回兩點(diǎn)所在大圓劣弧對應(yīng)圓心角，0=angle=pi+pi)dlng-=pi+pi;if(dlngpi)dlng=pi+pi-dlng;lat1*=pi/180,lat2*=pi/180;returnacos(cos(lat1)*cos(lat2)*cos(dlng)+sin(lat1)*sin(lat2);/計(jì)算距離,r 為球半徑doubleline_dist(doubler,doublelng1,doublelat1,doublelng2,doublelat2)doubledlng=fabs(lng1-lng2)*pi/180;while(dlng=pi+pi)dlng-=pi+pi;if(dlngp