题意：已知起点、圆、矩形，要求计算从起点开始，经过圆（和圆上任一点接触即可），到达矩形的路径的最短距离。（可以穿过园）。
分析：没什么好的方法，凭感觉圆上的每个点对应最短距离，应该是一个凸函数，用三分来解。不过应该是分成两部分，用两次三分来解。具体原因不明，通过实验只能得出三分必须是针对一个凸函数，很明显，从0~2*pi不是一个凸函数，但同理，0~pi，pi~2*pi也不一定是个凸函数。个人认为，网络上流传的[0,pi][pi,2*pi]这种分法，并不存在合理性。继续思考= =
另外，直接暴力枚举也是能过的。
错误：分析圆上的点与矩形的位置关系写挫了，虽然现在还是研究不明白到底出了什么问题，应该是边界吧。
double rec(double x,double y)
{
check();
if(x-xi<eps&&y-yj>eps)
return len(x,y,xi,yj);
else if(x-xi<eps&&y-yi<eps)
return len(x,y,xi,yi);
else if(x-xj>eps&&y-yj>eps)
return len(x,y,xj,yj);
else if(x-xj>eps&&y-yi<eps)
return len(x,y,xj,yj); if(x-xi>eps&&x-xj<eps)
if(y-yj>eps)
return fabs(y-yj);
else if(y-yi<eps)
return fabs(yi-y);
else if(y-yi>eps&&y-yj<eps)
if(x-xi<eps)
return fabs(xi-x);
else if(x-xj>eps)
return fabs(x-xj);
}
错误的写法
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std; const double pi=acos(-1.0);
const double eps=1e-; double sx,sy;
double rx,ry,r;
double xi,yi,xj,yj; double degree()
{
return atan((ry-sy)/(rx-sx));
} double len(double x,double y,double a,double b)
{
return sqrt((x-a)*(x-a)+(y-b)*(y-b));
} void change(double& x,double &y)
{
double p;
p=x;
x=y;
y=p;
} void check()
{
if(xi>xj)
change(xi,xj);
if(yi>yj)
change(yi,yj);
} double rec(double x,double y)
{
double lenx=,leny=;
check();
if(x<xi)
lenx=xi-x;
else if(x>xj)
lenx=x-xj;
if(y<yi)
leny=yi-y;
else if(y>yj)
leny=y-yj;
return sqrt(lenx*lenx+leny*leny);
} double f(double m)
{
double dx=rx+r*cos(m);
double dy=ry+r*sin(m); double len1=len(dx,dy,sx,sy);
double len2=rec(dx,dy); return len1+len2;
} int main()
{
int n;
while(~scanf("%lf%lf",&sx,&sy))
{
if(fabs(sx)<eps&&fabs(sy)<eps)
return ;
scanf("%lf%lf%lf",&rx,&ry,&r);
scanf("%lf%lf%lf%lf",&xi,&yi,&xj,&yj); double l=degree(),r=l+pi;
while(fabs(r-l)>eps)
{
double m1=l+(r-l)/;
double m2=r-(r-l)/;
if(f(m1)<f(m2))
r=m2;
else
l=m1;
}
double l1=l;
l=degree()+pi;r=l+pi;
while(fabs(r-l)>eps)
{
double m1=l+(r-l)/;
double m2=r-(r-l)/;
if(f(m1)<f(m2))
r=m2;
else
l=m1;
}
double l2=l;
printf("%.2f\n",min(f(l1),f(l2)));
}
return ;
}
暴力枚举，奇葩的精度。不过相比较而言，这个算法根据有可信度。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std; const double INF=1e10;
const double pi=acos(-1.0);
const double eps=1e-; double sx,sy;
double rx,ry,r;
double xi,yi,xj,yj; double len(double x,double y,double a,double b)
{
return sqrt((x-a)*(x-a)+(y-b)*(y-b));
} void change(double& x,double &y)
{
double p;
p=x;
x=y;
y=p;
} void check()
{
if(xi>xj)
change(xi,xj);
if(yi>yj)
change(yi,yj);
} double rec(double x,double y)
{
double lenx=,leny=;
check();
if(x<xi)
lenx=xi-x;
else if(x>xj)
lenx=x-xj;
if(y<yi)
leny=yi-y;
else if(y>yj)
leny=y-yj;
return sqrt(lenx*lenx+leny*leny);
} double f(double m)
{
double dx=rx+r*cos(m);
double dy=ry+r*sin(m); double len1=len(dx,dy,sx,sy);
double len2=rec(dx,dy); return len1+len2;
} int main()
{
int n;
while(~scanf("%lf%lf",&sx,&sy))
{
if(fabs(sx)<eps&&fabs(sy)<eps)
return ;
scanf("%lf%lf%lf",&rx,&ry,&r);
scanf("%lf%lf%lf%lf",&xi,&yi,&xj,&yj); double m=INF;
for(double i=;i<=;i+=0.01)
{
m=min(m,f(i/*pi));
}
printf("%.2f\n",m);
}
return ;
}