**题意:

      求点到圆,然后在到矩形的最短路.

思路:
**

把圆切成两半,然后对于每一半这个答案都是凸性的,最后输出两半中小的那个就行了,其中有一点,就是求点到矩形的距离,点到矩形的距离就是点到矩形四条边距离中最小的哪一个,求的方法有很多,一开始想都没想直接敲了个三分(这样就是两重三分了)跑了890ms AC的,后来看了看人家的都是直接用模板过的,我也找了个模板,结果31ms AC,哎,没事真的多暂歇模板,只有好处没坏处是了..

#include
#include
#include

#define eps 1e-3
double PI=acos(-1.0**);

using namespace** std**;

typedef struct
{
double** x ,y; }NODE**;

typedef struct
{**
NODE A ,B; }EDGE;

NODE node[10];
EDGE edge[10];
NODE S ,O; double diss1[10] ,diss2[10]; double R**;

bool** camp(NODE a ,NODE b) { return a.x < b.x || a.x == b.x && a.y < b.y**;
}

double** dis(NODE a ,NODE b) { double tmp = pow(a.x - b.x ,2.0) + pow(a.y - b.y ,2.0); return sqrt(tmp**);
}

double** minn(double x ,double y) { return x < y ? x : y**;
}

double** abss(double x) { return x > 0 ? x : -x; }

NODE getnode(double du) {
NODE ans;
ans.x = O.x + R *cos(du);
ans.y = O.y + R * sin(du); return ans; }

//**********************************
struct Point { double x,y;
Point(double xx=0,double yy=0):x(xx),y(yy){}
Point operator -(const Point p1) { return Point(x-p1.x,y-p1.y); } double operator ^(const Point p1) { return x*p1.x+y*p1.y; } }; double cross(Point a,Point b) { return a.x*b.y-a.y*b.x; } inline int sign(double d) { if(d>eps)return 1; else if(d<-eps)return -1; else return 0; } double dis(Point A ,Point B) { return sqrt(pow(A.x - B.x ,2.0) + pow(A.y - B.y ,2.0)); } double ptoline(Point tp,Point st,Point ed)//求点到线段的距离
{ double t1=dis(tp,st); double t2=dis(tp,ed); double ans=min(t1,t2); if(sign((ed-st)^(tp-st))>=0 && sign((st-ed)^(tp-ed))>=0)//锐角
{ double h=fabs(cross(st-tp,ed-tp))/dis(st,ed);
ans=min(ans,h); } return ans; }
//************************
double search3_2(double L ,double R) { double low ,up ,mid ,mmid;
NODE now;
low = L ,up = R; while(1) {
mid = (low + up) / 2;
now = getnode(mid);
Point A ,B ,C;
A.x = now.x ,A.y = now.y; for(int i = 1 ;i <= 4 ;i ++) {
B.x = edge[i].B.x ,B.y = edge[i].B.y;
C.x = edge[i].A.x ,C.y = edge[i].A.y;
diss1[i] = ptoline(A ,B ,C) + dis(S ,now**);

  }**  
  sort**(**diss1 **+** 1 **,**diss1 **+** 4 **+** 1**);**  
  mmid **= (**mid **+** up**) /** 2**;**  
  now **=** getnode**(**mmid**);**

  A**.**x **=** now**.**x **,**A**.**y **=** now**.**y**;  
  for(int** i **=** 1 **;**i **<=** 4 **;**i **++)  
  {**  
     B**.**x **=** edge**\[**i**\].**B**.**x **,**B**.**y **=** edge**\[**i**\].**B**.**y**;**  
     C**.**x **=** edge**\[**i**\].**A**.**x **,**C**.**y **=** edge**\[**i**\].**A**.**y**;**  
     diss2**\[**i**\] =** ptoline**(**A **,**B **,**C**) +** dis**(**S **,**now**);  
  }**  
  sort**(**diss2 **+** 1 **,**diss2 **+** 4 **+** 1**);  
  if(**diss1**\[**1**\] >** diss2**\[**1**\])** low **=** mid**;  
  else** up **=** mmid**;  
  if(**abss**(**low **-** up**) <** eps**) break;  

}
return** diss1[1**];
}

int main ()
{
while(~scanf(**"%lf %lf" *,&S.*x *,&S.y)) { if(S.*x *==* 0 && S.y == 0) break;
scanf("%lf %lf %lf" ,&O.x ,&O.y ,&R);
scanf("%lf %lf %lf %lf" ,&node[1].x ,&node[1].y ,&node[2].x ,&node[2].y);
node[3].x = node[1].x ,node[3].y = node[2].y;
node[4].x = node[2].x ,node[4].y = node[1].y;
sort(node + 1 ,node + 4 + 1 ,camp);
edge[1].A.x = node[1].x ,edge[1].A.y = node[1].y;
edge[1].B.x = node[2].x ,edge[1].B.y = node[2].y;
edge[2].A.x = node[2].x ,edge[2].A.y = node[2].y;
edge[2].B.x = node[4].x ,edge[2].B.y = node[4].y;
edge[3].A.x = node[4].x ,edge[3].A.y = node[4].y;
edge[3].B.x = node[3].x ,edge[3].B.y = node[3].y;
edge[4].A.x = node[3].x ,edge[4].A.y = node[3].y;
edge[4].B.x = node[1].x ,edge[4].B.y = node[1].y;
printf("%.2lf\n" ,minn(search3_2(0 ,PI) ,search3_2(PI ,2*PI))); } return 0; }