2019西安邀请赛 Angel's Journey 计算几何

题目链接：https://nanti.jisuanke.com/t/39270

题意：求A到B的最短距离

题解：若B在1 3 区域，那就是圆弧AD+直线BD，若B在2区域，那么先以B做圆的切线切点为C，结果为，BC+圆弧AC，要注意切点的位置是在左边还是右边

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const double PI=acos(-1.0);
#define eps 1e-8
int sgn(double x)
{if(fabs(x) < eps) return 0;if(x<0) return -1;return 1;
}
struct Point{double x,y;Point(){}Point(double x_,double y_){x=x_;y=y_;}Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);}Point operator +(const Point &b)const{return Point(x+b.x,y+b.y);}double operator *(const Point &b)const{return x*b.x + y*b.y;}double operator ^(const Point &b)const{return x*b.y - y*b.x;}Point operator *(const double &b)const{return Point(x*b , y*b);}Point operator /(const double &b)const{return Point(x/b , y/b);}double distance(Point p){return hypot(x-p.x,y-p.y);}double len(){return hypot(x,y);}double len2(){return x*x+y*y;}Point trunc(double xx){double l=len();if(!sgn(l) ) return *this;xx/=l;return Point(x*xx,y*xx);}Point rotleft(){return Point(-y,x);}Point rotright(){return Point(y,-x);}};
struct Line{Point s,e;Line(){}Line(Point s_,Point e_){s=s_;e=e_;}double length(){return s.distance(e);}
}; // p yuan xin
double r;int tangentline(Point p,Point q,Line &u,Line &v)
{double d=p.distance(q);double l=r*r/d;double h=sqrt(r*r-l*l);u=Line(q,p+((q-p).trunc(l)+(q-p).rotleft().trunc(h)));v=Line(q,p+((q-p).trunc(l)+(q-p).rotright().trunc(h)));return 1;
}
int main()
{int T;double rx,ry;double x,y;double ans1,ans2;Line u,v;Point p,oxin;Point t1,t2;Point downzuo,downyou;double j1,j2;double aa,bb,cc;scanf("%d",&T);while(T--){scanf("%lf%lf%lf%lf%lf",&rx,&ry,&r,&x,&y);oxin.x=rx;oxin.y=ry;p.x=x;p.y=y;if(x>=rx+r || x<=rx-r){printf("%.4f\n",PI*r/2+min(p.distance(Point(rx+r,ry)), p.distance(Point(rx-r,ry))));continue;}tangentline(oxin,p,u,v);t1=u.e;t2=v.e; downzuo.x=rx-r;downzuo.y=ry;if(t1.x>rx){downzuo.x=rx+r;downzuo.y=ry;}	aa=t1.distance(downzuo);bb=t1.distance(oxin);cc=downzuo.distance(oxin);j1=acos((bb*bb+cc*cc-aa*aa)/2/bb/cc);ans1=PI*r/2+j1*r+p.distance(t1);downyou.x=rx-r;downyou.y=ry;if(t2.x>rx){downyou.x=rx+r;downyou.y=ry;}aa=t2.distance(downyou);bb=t2.distance(oxin);cc=downyou.distance(oxin);j2=acos((bb*bb+cc*cc-aa*aa)/2/bb/cc);ans2=PI*r/2+j2*r+p.distance(t2);printf("%.4f\n",min(ans1,ans2));}return 0;
}