表示这个题目很坑，竟然普通的枚举角度也能过，在现场如果没敢这么干的童鞋肯定后悔死了，不过直接枚举跑的时间还是没三分枚举快的
三分枚举的思想其实和二分差不多，具体为什么对，看看代码是怎么枚举的，稍微想想就能明白了！
直接枚举：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define eps 1e-8
using namespace std;
#define PI acos(-1.0)
struct point
{
double x;
double y;
point(double a=0,double b=0):x(a),y(b){}
}a,b,c,d,pos,temp1,temp2,start;
double r;
double cross(point p0, point p1, point p2)//j计算差乘
{ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}
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 disptoseg(point p,point l1,point l2)
{
point t=p;
t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;
if(cross(l1,t,p)*cross(l2,t,p)>eps)
return dis(p,l1) < dis(p,l2) ? dis(p,l1):dis(p,l2);
return fabs(cross(p,l1,l2)/dis(l1,l2));
}
double distotri(point p)
{
return min(disptoseg(p,a,b),min(disptoseg(p,b,d),min(disptoseg(p,d,c),disptoseg(p,c,a))));
}
point make_p(double l)
{
return point(pos.x+r*cos(l),pos.y+r*sin(l));
}
double find_dis(point p)
{
return dis(p,start)+distotri(p);
}
double find_ans()
{
double ans=1e10;
double mid=0;
double over=PI*2,k;
point p;
for(mid=0;mid<=over;mid+=1e-3)
{
p=make_p(mid);
k=find_dis(p);
if(ans > k)
ans=k;
}
return ans;
}
int main()
{
while(scanf("%lf%lf",&start.x,&start.y))
{
if(start.x==0 && start.y==0)
return 0;
scanf("%lf%lf%lf",&pos.x,&pos.y,&r);
scanf("%lf%lf%lf%lf",&temp1.x,&temp1.y,&temp2.x,&temp2.y);
if(temp1.x > temp2.x)
c=temp1,temp1=temp2,temp2=c;
if(temp1.y > temp2.y)
a=temp1,d=temp2,b.x=d.x,b.y=a.y,c.x=a.x,c.y=d.y;
else
c=temp1,b=temp2,a.x=c.x,a.y=b.y,d.x=b.x,d.y=c.y;
printf("%.2lf\n",find_ans());
}
return 0;
}
三分枚举：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define eps 1e-8
using namespace std;
#define PI acos(-1.0)
struct point
{
double x;
double y;
point(double a=0,double b=0):x(a),y(b){}
}a,b,c,d,pos,temp1,temp2,start;
double r;
double cross(point p0, point p1, point p2)//j计算差乘
{ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}
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 disptoseg(point p,point l1,point l2)
{
point t=p;
t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;
if(cross(l1,t,p)*cross(l2,t,p)>eps)
return dis(p,l1) < dis(p,l2) ? dis(p,l1):dis(p,l2);
return fabs(cross(p,l1,l2)/dis(l1,l2));
}
double distotri(point p)
{
return min(disptoseg(p,a,b),min(disptoseg(p,b,d),min(disptoseg(p,d,c),disptoseg(p,c,a))));
}
point make_p(double l)
{
return point(pos.x+r*cos(l),pos.y+r*sin(l));
}
double find_dis(point p)
{
return dis(p,start)+distotri(p);
}
double find_ans()
{
double l,r,ans1,ans2,t_2,t_4;
l=0,r=PI;
double mid_2,mid_4;
point p_2,p_4;
while(r-l>=eps)
{
mid_2=(l+r)/2;
mid_4=(mid_2+r)/2;
p_2=make_p(mid_2);
p_4=make_p(mid_4);
t_2=find_dis(p_2);
t_4=find_dis(p_4);
if(t_2 > t_4)
l=mid_2;
else
r=mid_4;
}
p_2=make_p(l);
ans1=find_dis(p_2);
l=PI,r=PI*2;
while(r-l>=eps)
{
mid_2=(l+r)/2;
mid_4=(mid_2+r)/2;
p_2=make_p(mid_2);
p_4=make_p(mid_4);
t_2=find_dis(p_2);
t_4=find_dis(p_4);
if(t_2 > t_4)
l=mid_2;
else
r=mid_4;
}
p_2=make_p(l);
ans2=find_dis(p_2);
return min(ans1,ans2);
}
int main()
{
while(scanf("%lf%lf",&start.x,&start.y))
{
if(start.x==0 && start.y==0)
return 0;
scanf("%lf%lf%lf",&pos.x,&pos.y,&r);
scanf("%lf%lf%lf%lf",&temp1.x,&temp1.y,&temp2.x,&temp2.y);
if(temp1.x > temp2.x)
c=temp1,temp1=temp2,temp2=c;
if(temp1.y > temp2.y)
a=temp1,d=temp2,b.x=d.x,b.y=a.y,c.x=a.x,c.y=d.y;
else
c=temp1,b=temp2,a.x=c.x,a.y=b.y,d.x=b.x,d.y=c.y;
printf("%.2lf\n",find_ans());
}
return 0;
}