hdu 2438+hdu 3400(三分求极值)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2438

网上大牛思路：

可以根据边界，汽车已经转弯，设水平方向为x轴，垂直方向为y轴。

则汽车的内边界(靠近里面的边界)的直线方程式f(x)为：y=x*tan(a)+l*sin(a)+d/cos(a).其中a是汽车与x轴的夹角

当y=X时，求解出的-x即为汽车的内边界到y轴的距离h，若h小于Y即可转弯，若大于Y就不能转弯。
所以只需要利用方程式，求-x的最大值，即可判断能否通过。
由于f(x)是凸函数(随着x的增大y先增大后减小)，所以，需要借助三分求解。

图示：

第一道三分求极值题啊！！！

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 #define MIN 1e-7
 7 #define PI acos(-1.0)
 8 double x,y,l,d;
 9 
10 double Solve(double tmp){
11     return (-x+l*sin(tmp)+d/cos(tmp))/tan(tmp);
12 }
13 
14 int main(){
15     while(~scanf("%lf%lf%lf%lf",&x,&y,&l,&d)){
16         double low=0,high=PI/2.0,mid,mmid;
17         if(x<d||y<d){ puts("no");continue; }
18         while( high-low>MIN ){
19             mid=(low+high)/2.0;
20             mmid=(mid+high)/2.0;
21             if(Solve(mid)>Solve(mmid))high=mmid+1e-9;
22             else low=mid-1e-9;
23         }
24         if(Solve(mid)<y){
25             puts("yes");
26         }else 
27             puts("no");
28     }
29     return 0;
30 }
31 
32 
33             
34

View Code

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3400

思路：

首先，时间最短的路径必定是至多3条直线段构成的，一条在AB上，一条在CD上，一条架在两条线段之间。其次，如果有一个固定的点，求到另外一条线段上的一个端点上的最短距离，怎么做呢，可以通过三分来解，应该可以想到，枚举线段上的两个端点作为左右两个端点。这样线段上每个点作为中间点的距离从固定点到线段上的端点的距离就构成了一个凹形函数，这样子就可以用三分枚举出最小值。接着我们就用三分枚举AB上的那个最小值点，通过确定的那个点，在CD上三分出最小值。这样子通过三分嵌套三分的算法。就可以确定出答案了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 #define eps 1e-7
 7 #define MIN 1e-9
 8 struct Point{
 9     double x,y;
10 }a,b,c,d,aa,dd;
11 double ab,cd;
12 double p,q,r;
13 
14 double dist(Point &a,Point &b){
15     //加eps，可能测试数据都是int类型开方有误差 
16     return sqrt(eps+(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
17 }
18 
19 double Solve(double t){
20     dd.x=d.x+(c.x-d.x)/cd*t*q;
21     dd.y=d.y+(c.y-d.y)/cd*t*q;
22     return t+dist(aa,dd)/r;
23 }
24 
25 double SanFen(double t){
26     aa.x=a.x+(b.x-a.x)/ab*t*p;
27     aa.y=a.y+(b.y-a.y)/ab*t*p;
28     double low=0,high=cd/q,mid,mmid;//对cd进行三分
29     while(high-low>eps){
30         mid=(low+high)/2;
31         mmid=(mid+high)/2;
32         if(Solve(mid)<Solve(mmid))high=mmid+MIN;
33         else low=mid-MIN;
34     }
35     return t+Solve(mid);
36 }
37 
38 int main(){
39     int _case;
40     scanf("%d",&_case);
41     while(_case--){
42         scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
43         scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);
44         scanf("%lf%lf%lf",&p,&q,&r);
45         ab=dist(a,b),cd=dist(c,d);
46         double low=0,high=ab/p,mid,mmid;//对ab进行三分
47         while(high-low>eps){
48             mid=(low+high)/2;
49             mmid=(mid+high)/2;
50             if(SanFen(mid)<SanFen(mmid))high=mmid+MIN;
51             else low=mid-MIN;
52         }
53         //最后通过ab上确定的那个点再在cd上进行三分求出最小值
54         printf("%.2lf\n",SanFen(mid));
55     }
56     return 0;
57 }

View Code