HDU 4454 - Stealing a Cake（三分）
我比较快速的想到了三分，但是我是从0到2*pi区间进行三分，并且漏了一种点到边距离的情况，一直WA了好几次

后来画了下图才发现，0到2*pi区间内是有两个极值的，每个半圆存在一个极值

以下是代码

#include <cstdio>#include <cmath>#include <algorithm>#define pi acos(-1.0)using namespace std;typedef struct{    double x;    double y;}point;typedef struct{    double x;    double y;    double r;}circle;typedef struct{    point s;    point e;}line;double dis(point a,point b){    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}double cal(point st,line ed,circle c,double t){    point p;    p.x=c.x+cos(t)*c.r;    p.y=c.y+sin(t)*c.r;    if(fabs(ed.s.x-ed.e.x)<1e-8)    {        if(p.y>ed.s.y&&p.y<ed.e.y)        {            return dis(p,st)+fabs(p.x-ed.s.x);        }        else        {            double t=min(dis(p,ed.s),dis(p,ed.e));            return dis(p,st)+t;        }    }    if(fabs(ed.s.y-ed.e.y)<1e-8)    {        if(p.x>ed.s.x&&p.x<ed.e.x)        {            return dis(p,st)+fabs(p.y-ed.s.y);        }        else        {            double t=min(dis(p,ed.s),dis(p,ed.e));            return dis(p,st)+t;        }    }    return -1;}double solve1(point st,line ed,circle c){    double L=0,R=pi,mid=(L+R)/2,midmid=(mid+R)/2;    while(R-L>1e-10)    {        if(cal(st,ed,c,mid)<cal(st,ed,c,midmid))R=midmid;        else L=mid;        mid=(L+R)/2;        midmid=(R+mid)/2;    }    return cal(st,ed,c,midmid);}double solve2(point st,line ed,circle c){    double L=pi,R=2*pi,mid=(L+R)/2,midmid=(mid+R)/2;    while(R-L>1e-10)    {        if(cal(st,ed,c,mid)<cal(st,ed,c,midmid))R=midmid;        else L=mid;        mid=(L+R)/2;        midmid=(R+mid)/2;    }    return cal(st,ed,c,midmid);}int main(){    double m,x[2],y[2];    point st;    circle cir;    line a[4];    while(scanf("%lf%lf",&st.x,&st.y)==2)    {        if(!st.x&&!st.y)break;        scanf("%lf%lf%lf",&cir.x,&cir.y,&cir.r);        scanf("%lf%lf",&x[0],&y[0]);        scanf("%lf%lf",&x[1],&y[1]);        if(x[0]>x[1]) swap(x[0],x[1]);        if(y[0]>y[1]) swap(y[0],y[1]);        a[0].s.x=x[0];a[0].s.y=y[0];        a[0].e.x=x[0];a[0].e.y=y[1];        a[1].s.x=x[0];a[1].s.y=y[0];        a[1].e.x=x[1];a[1].e.y=y[0];        a[2].s.x=x[1];a[2].s.y=y[0];        a[2].e.x=x[1];a[2].e.y=y[1];        a[3].s.x=x[0];a[3].s.y=y[1];        a[3].e.x=x[1];a[3].e.y=y[1];        m=1e18;        for(int i=0;i<4;i++)        {            double t=solve1(st,a[i],cir);            if(t<m)m=t;            t=solve2(st,a[i],cir);            if(t<m)m=t;        }        printf("%.2lf\n",m);    }    return 0;}