acm-计算几何模板

#includebits/stdc++.husingnamespacestd;constdoubleeps=1e-8;constdoubleINF=1e20;constdoublepi=acos(-1.0);intdcmp(doublex){if(fabs(x)eps)return0;return(x0?-1:1);}inlinedoublesqr(doublex){returnx*x;}//*************点structPoint{doublex,y;Point(double_x=0,double_y=0):x(_x),y(_y){}voidinput(){scanf(%lf%lf,&x,&y);}voidoutput(){printf(%.2f%.2f\n,x,y);}booloperator==(constPoint&b)const{return(dcmp(x-b.x)==0&&dcmp(y-b.y)==0);}booloperator(constPoint&b)const{return(dcmp(x-b.x)==0?dcmp(y-b.y)0:xb.x);}Pointoperator+(constPoint&b)const{returnPoint(x+b.x,y+b.y);}Pointoperator-(constPoint&b)const{returnPoint(x-b.x,y-b.y);}Pointoperator*(doublea){returnPoint(x*a,y*a);}Pointoperator/(doublea){returnPoint(x/a,y/a);}doublelen2(){//返回长度的平方returnsqr(x)+sqr(y);}doublelen(){//返回长度returnsqrt(len2());}Pointchange_len(doubler){//转化为长度为r的向量doublel=len();if(dcmp(l)==0)return*this;//零向量返回自身r/=l;returnPoint(x*r,y*r);}Pointrotate_left(){//顺时针旋转90度returnPoint(-y,x);}Pointrotate_right(){//逆时针旋转90度returnPoint(y,-x);}Pointrotate(Pointp,doubleang){//绕点p逆时针旋转angPointv=(*this)-p;doublec=cos(ang),s=sin(ang);returnPoint(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);}Pointnormal(){//单位法向量doublel=len();returnPoint(-y/l,x/l);}};doublecross(Pointa,Pointb){//叉积returna.x*b.y-a.y*b.x;}doubledot(Pointa,Pointb){//点积returna.x*b.x+a.y*b.y;}doubledis(Pointa,Pointb){//两个点的距离Pointp=b-a;returnp.len();}doublerad_degree(doublerad){//弧度转化为角度returnrad/pi*180;}doublerad(Pointa,Pointb){//两个向量的夹角returnfabs(atan2(fabs(cross(a,b)),dot(a,b)));}boolparallel(Pointa,Pointb){//向量平行doublep=rad(a,b);returndcmp(p)==0||dcmp(p-pi)==0;}//************直线线段structLine{Points,e;//直线的两个点Line(){}Line(Point_s,Point_e):s(_s),e(_e){}//一个点和倾斜角确定直线Line(Pointp,doubleang){s=p;if(dcmp(ang-pi/2)==0){e=s+Point(0,1);}elsee=s+Point(1,tan(ang));}//ax+by+c=0确定直线Line(doublea,doubleb,doublec){if(dcmp(a)==0){s=Point(0,-c/b);e=Point(1,-c/b);}elseif(dcmp(b)==0){s=Point(-c/a,0);e=Point(-c/a,1);}else{s=Point(0,-c/b);e=Point(1,(-c-a)/b);}}voidinput(){s.input();e.input();}voidadjust(){if(es)swap(e,s);}doublelength(){//求线段长度returndis(s,e);}doubleangle(){//直线的倾斜角doublek=atan2(e.y-s.y,e.x-s.x);if(dcmp(k)0)k+=pi;if(dcmp(k-pi)==0)k-=pi;returnk;}};intrelation(Pointp,Linel){//点和直线的关系//1:在左侧2:在右侧3:在直线上intc=dcmp(cross(p-l.s,l.e-l.s));if(c0)return1;elseif(c0)return2;elsereturn3;}boolpoint_on_seg(Pointp,Linel){//判断点在线段上returndcmp(cross(p-l.s,l.e-l.s))==0&&dcmp(dot(p-l.s,p-l.e)=0);//如果忽略端点交点改成小于号就好了}boolparallel(Linea,Lineb){//直线平行returnparallel(a.e-a.s,b.e-b.s);}intseg_cross_seg(Linea,Linev){//线段相交判断//1:规范相交2:不规范相交0:不相交intd1=dcmp(cross(a.e-a.s,v.s-a.s));intd2=dcmp(cross(a.e-a.s,v.e-a.s));intd3=dcmp(cross(v.e-v.s,a.s-v.s));intd4=dcmp(cross(v.e-v.s,a.e-v.s));if((d1^d2)==-2&&(d3^d4)==-2)return2;return(d1==0&&dcmp(dot(v.s-a.s,v.s-a.e))=0)||(d2==0&&dcmp(dot(v.e-a.s,v.e-a.e))=0)||(d3==0&&dcmp(dot(a.s-v.s,a.s-v.e))=0)||(d4==0&&dcmp(dot(a.e-v.s,a.e-v.e))=0);}intline_cross_seg(Linea,Linev){//直线和线段相交判断//1:非规范相交2:规范相交0:不相交intd1=dcmp(cross(a.e-a.s,v.s-a.s));intd2=dcmp(cross(a.e-a.s,v.e-a.s));if(d1^d2==-2)return2;return(d1==0||d2==0);}intline_cross_line(Linea,Linev){//直线相交判断//0:平行1:重合2:相交if(parallel(a,v))returnrelation(a.e,v)==3;return2;}Pointline_intersection(Linea,Linev){//直线交点//调用前确保有交点doublea1=cross(v.e-v.s,a.s-v.s);doublea2=cross(v.e-v.s,a.e-v.s);returnPoint((a.s.x*a2-a.e.x*a1)/(a2-a1),(a.s.y*a2-a.e.y*a1)/(a2-a1));}doublepoint_to_line(Pointp,Linea){//点到直线的距离returnfabs(cross(p-a.s,a.e-a.s)/a.length());}doublepoint_to_seg(Pointp,Linea){//点到线段的距离if(dcmp(dot(p-a.s,a.e-a.s))0||dcmp(dot(p-a.e,a.s-a.e))0)returnmin(dis(p,a.e),dis(p,a.s));returnpoint_to_line(p,a);}Pointprojection(Pointp,Linea){//点在直线上的投影returna.s+(((a.e-a.s)*dot(a.e-a.s,p-a.s))/(a.e-a.s).len2());}Pointsymmetry(Pointp,Linea){//点关于直线的对称点Pointq=projection(p,a);returnPoint(2*q.x-p.x,2*q.y-p.y);}//***************圆structCircle{//圆心半径Pointp;doubler;Circle(){}Circle(Point_p,double_r):p(_p),r(_r){}Circle(doublea,doubleb,double_r){p=Point(a,b);r=_r;}voidinput(){p.input();scanf(%lf,&r);}voidoutput(){p.output();printf(%.2f\n,r);}booloperator==(constCircle&a)const{returnp==a.p&&(dcmp(r-a.r)==0);}doublearea(){//面积returnpi*r*r;}doublecircumference(){//周长return2*pi*r;}};intrelation(Pointp,Circlea){//点和圆的关系//0:圆外1:圆上2:圆内doubled=dis(p,a.p);if(dcmp(d-a.r)==0)return1;return(dcmp(d-a.r)0?2:0);}intrelation(Linea,Circleb){//直线和圆的关系//0:相离1:相切2:相交doublep=point_to_line(b.p,a);if(dcmp(p-b.r)==0)return1;return(dcmp(p-b.r)0?2:0);}intrelation(Circlea,Circlev){//两圆的位置关系//1:内含2:内切3:相交4:外切5:相离doubled=dis(a.p,v.p);if(dcmp(d-a.r-v.r)0)return5;if(dcmp(d-a.r-v.r)==0)return4;doublel=fabs(a.r-v.r);if(dcmp(d-a.r-v.r)0&&dcmp(d-l)0)return3;if(dcmp(d-l)==0)return2;if(dcmp(d-l)0)return1;}Circleout_circle(Pointa,Pointb,Pointc){//三角形外接圆Lineu=Line((a+b)/2,((a+b)/2)+(b-a).rotate_left());Linev=Line((b+c)/2,((b+c)/2)+(c-b).rotate_left());Pointp=line_intersection(u,v);doubler=dis(p,a);returnCircle(p,r);}Circlein_circle(Pointa,Pointb,Pointc){//三角形内切圆Lineu,v;doublem=atan2(b.y-a.y,b.x-a.x),n=atan2(c.y-a.y,c.x-a.x)