本题可以枚举5000个点跑一下也能过.
考虑三分的话,我们发现随着角度的变化,他一定是一个凹函数+一个凸函数, 我们分两段跑圆的三分,一段是[0,pi],一段是[pi,pi*2],.不违背三分.
然后我想了一下,他肯定是一个凹函数+一个凸函数,一个函数都是由cosa,sina构成的,虽然有波折,但一定是有一个极大值,一个极小值.用我下面的二分是没有问题的,但如果使用的是mid = (l+r)/2; midd = (mid + r)/2 就可能会错.因为极小值就可能出现在(l,mid)中间,而如果cal(mid) 恰好大于cal(midd),就错了.
#include<cstdio> #include<iostream> #include<cmath> using namespace std; const double PI = acos(-1.0); const double eps = 1e-9; struct Point{ double x,y; }ant; struct circle{ double x,y,r; }cake; //rect double x1,x2,x3,x4,yy1,y2,y3,y4; double dis(double x1, double y1, double x2, double y2){ return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ); } double cal(double ang){ double x = cake.x + cake.r * cos(ang); double y = cake.y + cake.r * sin(ang); double ans = dis(ant.x, ant.y , x, y); double minx; if( (x1-x)*(x3-x) <= 0){ minx = min(fabs(y - yy1), fabs(y - y3)); }else if( (yy1-y)*(y3-y) <=0 ){ minx = min(fabs(x - x1), fabs(x - x3)); }else{ minx = min(dis(x, y, x1, yy1), dis(x, y, x2, y2)); minx = min(minx, dis(x, y, x3, y3)); minx = min(minx, dis(x, y, x4, y4)); } return ans + minx; } int main(){ while(~scanf("%lf%lf",&ant.x,&ant.y)){ if(fabs(ant.x) < eps && fabs(ant.y) < eps)break; scanf("%lf%lf%lf",&cake.x,&cake.y,&cake.r); scanf("%lf%lf%lf%lf",&x1,&yy1,&x3,&y3); x2 = x1; y2 = y3; x4 = x3; y4 = yy1; double l = 0 , r = PI*2, mid1, mid2; for(int i = 0; i < 200; i++){ mid1 = l + (r-l)/3; mid2 = r - (r-l)/3; if(cal(mid1) < cal(mid2)){ r = mid2; }else{ l = mid1; } } double ans = cal(l); ans = min(ans, cal(l)); printf("%.2lf\n",ans); } return 0; }然后这样的话,我的理解就是三分就是为了找一个函数的极大值或极小值,但如果这个函数有很多的曲折的话,我们就把他切开来,分段跑.
