常用计算几何函数.docx
《常用计算几何函数.docx》由会员分享，可在线阅读，更多相关《常用计算几何函数.docx（25页珍藏版）》请在冰点文库上搜索。
常用计算几何函数
#include
#include
#include
#include
#include
#include
#include
////hdu4063
usingnamespacestd;
#defineinf100000
#definepiacos（-1.0）
#defineeps1e-8
#definemaxn1500
#definesqr（x）（（x）*（x））
//
doublef[maxn][maxn];
doubledis[maxn];
intsign（doublex）{
if（x<-eps）return-1;
returnx>eps;
}
//hdu406339613982
structpoint{
doublex,y;
point（）{}
point（doublex,doubley）:
x（x）,y（y）{}
voidin（）{
scanf（"%lf%lf",&x,&y）;
}
booloperator==（constpoint&b）const{
returnsign（x-b.x）==0&&sign（y-b.y）==0;
}
};
pointp[maxn];
structcircle{
pointa;
doubler;
circle（）{}
circle（pointa,doubler）:
a（a）,r（r）{}
};
circleC[30];
structnode{
doublex1,x2;
};
nodeT[maxn];
boolcmp（nodea,nodeb）{
if（sign（a.x1-b.x1）==0）returnsign（a.x2-b.x2）<0;
returnsign（a.x1-b.x1）<0;
}
doublexmult（pointa,pointb,pointo）{
return（a.x-o.x）*（b.y-o.y）-（a.y-o.y）*（b.x-o.x）;
}
/*计算两点之间的距离*/
doubledist（pointa,pointb）{
doublex=a.x-b.x;
doubley=a.y-b.y;
returnsqrt（x*x+y*y）;
}
//求两条直线的交点
pointintersection（pointu1,pointu2,pointv1,pointv2）{
pointret=u1;
doublet=（（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;
}
/*求两个圆的交点*/
intcircle_intersect（circleA,circleB,point&ia,point&ib）{
if（A.a.x==B.a.x&&A.a.y==B.a.y）
return5;
doubledd=dist（A.a,B.a）;
if（A.r+B.r+epsdoublek,a,b,d,aa,bb,cc,c,drt;
k=A.r;
a=B.a.x-A.a.x;
b=B.a.y-A.a.y;
c=B.r;
d=sqr（c）-sqr（k）-sqr（a）-sqr（b）;
aa=4*sqr（a）+4*sqr（b）;
bb=4*b*d;
cc=sqr（d）-4*sqr（a）*sqr（k）;
drt=sqr（bb）-4*aa*cc;
if（drt<0）
return5;
drt=sqrt（drt）;
ia.y=（-bb+drt）/2/aa;
ib.y=（-bb-drt）/2/aa;
if（abs（a）{
ia.x=sqrt（sqr（k）-sqr（ia.y））;
ib.x=-ia.x;
}
else
{
ia.x=（2*b*ia.y+d）/-2/a;
ib.x=（2*b*ib.y+d）/-2/a;
}
ia.x+=A.a.x;
ia.y+=A.a.y;
ib.x+=A.a.x;
ib.y+=A.a.y;
if（abs（ia.y-ib.y）{
if（abs（A.r+B.r-dd）return2;
if（abs（dd-（max（A.r,B.r）-min（A.r,B.r）））return3;
}
return4;
}
//点到直线的距离
doubledisptoline（pointp,pointl1,pointl2）{
returnfabs（xmult（p,l1,l2））/dist（l1,l2）;
}
//圆与直线的交点
voidintersection_line_circle（pointc,doubler,pointl1,pointl2,point&p1,point&p2）{
pointp=c;
doublet;
p.x+=l1.y-l2.y;
p.y+=l2.x-l1.x;
p=intersection（p,c,l1,l2）;
t=sqrt（r*r-dist（p,c）*dist（p,c））/dist（l1,l2）;
p1.x=p.x+（l2.x-l1.x）*t;
p1.y=p.y+（l2.y-l1.y）*t;
p2.x=p.x-（l2.x-l1.x）*t;
p2.y=p.y-（l2.y-l1.y）*t;
}
voidswap（double&x1,double&y1）{
doublex=x1;
x1=y1;
y1=x;
}
doubledijkstra（intst,inten,intm）{
inti,j,k,l;
intvis[maxn];
memset（vis,0,sizeofvis）;
for（i=0;idis[i]=f[st][i];
dis[st]=0;
vis[st]=1;
for（i=1;iintpos=-1;
doublemin_len=inf;
for（j=1;jif（vis[j]）continue;
if（dis[j]}
if（pos==-1）break;
vis[pos]=1;
for（j=1;jif（!
vis[j]&&dis[j]>dis[pos]+f[pos][j]+eps）{
dis[j]=dis[pos]+f[pos][j];
}
}
returndis[en];
}
intmain（）{
intt,i,j,n;
intTT=0;
scanf（"%d",&t）;
while（t--）{
scanf（"%d",&n）;
for（i=0;iC[i].a.in（）;
scanf（"%lf",&C[i].r）;
}
pointstar,end;
star=C[0].a;end=C[n-1].a;
intcnt=0;
for（i=0;iintflag=1;
for（j=0;jdoublel=dist（C[i].a,C[j].a）;
if（sign（C[j].r-C[i].r-l）>0）{flag=0;break;}
}
if（flag）C[cnt++]=C[i];
}
n=cnt;//留下的圆的个数
cnt=0;
for（i=0;ifor（j=i+1;jdoublel=dist（C[i].a,C[j].a）;
if（sign（l-C[i].r-C[j].r）>0）continue;
pointu,v;
circle_intersect（C[i],C[j],u,v）;
p[cnt++]=u;p[cnt++]=v;
}
}
intm=0;//这个图中点的个数
for（i=0;iintflag=1;
for（j=i+1;jif（p[i]==p[j]）{flag=0;break;}
if（flag）p[m++]=p[i];
}
intst=-1,en=-1;
for（i=0;iif（p[i]==star）{st=i;}
elseif（p[i]==end）{en=i;}
if（st!
=-1&&en!
=-1）break;
}
if（st==-1）{
for（i=m-1;i>=0;i--）
p[i+1]=p[i];
p[0]=star;
m++;
st=0;
}
if（en==-1）{p[m++]=end;en=m-1;}
if（st==en||star==end）{printf（"Case%d:
",++TT）;printf（"0.0000\n"）;continue;}
/*
printf（"点的信息***%d\n",m）;
for（i=0;iprintf（"%d%lf%lf\n",i,p[i].x,p[i].y）;
}
printf（"圆的信息:
%d\n",n）;
for（i=0;iprintf（"%lf%lf%lf\n",C[i].a.x,C[i].a.y,C[i].r）;
}*/
for（i=0;ifor（j=i+1;jintc=0;
pointu,v;
for（intl=0;ldoublelen=disptoline（C[l].a,p[i],p[j]）;
if（sign（len-C[l].r）>0）continue;
intersection_line_circle（C[l].a,C[l].r,p[i],p[j],u,v）;
T[c].x1=u.x;T[c++].x2=v.x;
}
intnum=0;
doublexx=min（p[i].x,p[j].x）,yy=max（p[i].x,p[j].x）;
for（intl=0;lif（sign（T[l].x1-T[l].x2）>0）swap（T[l].x1,T[l].x2）;
if（sign（T[l].x2-xx）<=0）continue;
if（sign（T[l].x1-yy）>=0）continue;
T[num++]=T[l];
}
c=num;
sort（T,T+c,cmp）;
doublemax_hi=T[0].x2;
for（intl=1;lif（sign（T[l].x1-max_hi）<=0）max_hi=max（max_hi,T[l].x2）;
elsebreak;
}
if（sign（T[0].x1-xx）<=0&&sign（max_hi-yy）>=0）f[i][j]=f[j][i]=dist（p[i],p[j]）;
elsef[i][j]=f[j][i]=inf;
}
/*
printf（"边长的信息：
%d\n",m）;
for（i=0;ifor（j=0;jprintf（"%lf",f[i][j]）;
printf（"\n"）;
}*/
doubleans=dijkstra（st,en,m）;
printf（"Case%d:
",++TT）;
if（sign（ans-inf）>=0）printf（"Nosuchpath.\n"）;
elseprintf（"%.4lf\n",ans）;
}
return0;
}
#include
#include
#include
#include
#include
#include
#include
usingnamespacestd;
#definepiacos（-1.0）
#defineeps1e-8
#definemaxn105
intsign（doublex）{
if（x<-eps）return-1;
returnx>eps;
}
structpoint{
doublex,y;
point（）{}
point（doublex,doubley）:
x（x）,y（y）{}
voidin（）{
scanf（"%lf%lf",&x,&y）;
}
pointoperator-（constpoint&b）const{
returnpoint（x-b.x,y-b.y）;
}
pointoperator+（constpoint&b）const{
returnpoint（x+b.x,y+b.y）;
}
booloperator==（constpoint&b）const{
returnsign（x-b.x）==0&&sign（y-b.y）==0;
}
};
pointp[maxn];
pointsun,er;
doublet1,t2,t,r;
doublexmult（pointa,pointb,pointo）{
return（a.x-o.x）*（b.y-o.y）-（a.y-o.y）*（b.x-o.x）;
}
//求两条直线的交点
pointintersection（pointu1,pointu2,pointv1,pointv2）{
pointret=u1;
doublet=（（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;
}
//求三角形重心
pointbarycenter（pointa,pointb,pointc）{
pointu1,u2,v1,v2;
u1.x=（a.x+b.x）/2;
u1.y=（a.y+b.y）/2;
u2=c;
v1.x=（a.x+c.x）/2;
v1.y=（a.y+c.y）/2;
v2=b;
returnintersection（u1,u2,v1,v2）;
}
//求多边形重心（顺时针、逆时针都可以）
pointbarycenter（intn,point*P）{//求重心
pointret,t;
doublet1=0,t2;
inti;
ret.x=ret.y=0;
for（i=1;iif（fabs（t2=xmult（p[0],p[i],p[i+1]））>eps）{
t=barycenter（p[0],p[i],p[i+1]）;
ret.x+=t.x*t2;
ret.y+=t.y*t2;
t1+=t2;
}
if（fabs（t1）>eps）ret.x/=t1,ret.y/=t1;
returnret;
}
doubledist（pointa,pointb）{
doublex=a.x-b.x;
doubley=a.y-b.y;
returnsqrt（x*x+y*y）;
}
pointrotate（pointa,doubleang）{//将向量旋转角度（逆时针）
pointres;
res.x=a.x*cos（ang）-a.y*sin（ang）;
res.y=a.x*sin（ang）+a.y*cos（ang）;
returnres;
}
boolcmp1（pointa,pointb）{
if（sign（a.y-b.y）<0）returntrue;
elseif（sign（a.x-b.x）<0）returntrue;
returnfalse;
}
boolcmp（pointa,pointb）{
if（sign（xmult（a,b,er））>0）returntrue;
returnfalse;
}
doubledisptoline（pointp,pointl1,pointl2）{//点到直线的距离
returnfabs（xmult（p,l1,l2））/dist（l1,l2）;
}
pointintersection_line_circle（pointc,doubler,pointl1,pointl2）{//圆与直线的交点
pointp=c;
doublet;
p.x+=l1.y-l2.y;
p.y+=l2.x-l1.x;
p=intersection（p,c,l1,l2）;
t=sqrt（r*r-dist（p,c）*dist（p,c））/dist（l1,l2）;
pointp1,p2;
p1.x=p.x+（l2.x-l1.x）*t;
p1.y=p.y+（l2.y-l1.y）*t;
p2.x=p.x-（l2.x-l1.x）*t;
p2.y=p.y-（l2.y-l1.y）*t;//两个交点取一个更近的
if（sign（dist（p1,sun）-dist（p2,sun））>=0）returnp2;
returnp1;
}
voiddot_line_cirlce（pointp,pointo,doubler,point&p1,point&p2）{//点p在圆上的两个切点
doublelen=dist（p,o）,ce=sqrt（len*len-r*r）;
doubleang=acos（ce/len）;
pointu=o-p;
u.x=u.x*ce/len;
u.y=u.y*ce/len;
p1=rotate（u,ang）;
p1=p+p1;
p2=rotate（u,-ang）;
p2=p2+p;
return;
}
//判断u在线段l1l2之内
boolsame_line_side（pointu,pointl1,pointl2）{
if（sign（（l1.x-u.x）*（l2.x-u.x））<=0&&sign（（l1.y-u.y）*（l2.y-u.y））<=0）returntrue;
returnfalse;
}
intmain（）{
inti,n,j;
while（scanf（"%lf%lf",&sun.x,&sun.y）!
=EOF）{
er.in（）;
scanf（"%lf",&r）;
scanf（"%d%lf%lf%lf",&n,&t1,&t2,&t）;//公转自转
for（i=0;ipointcen=ba
升级会员 