HDu 3400(3点)

テーマリンク:クリックしてリンクを開く;題意:本題は2本の線分を与え、1本の線分の端点はa,bである.もう1つの線分の端点はc,dで、2つの線分と線分の上で異なる速度があって、最短時間を求めます.
分析:本題は全部で3つの時間があって、a-bの上で、c-dの上で、空白の地方にあります.3つの時間をx,y,zとしている.xとyが確定するとzは確定するので、このように2つの線分上の点が確定してzも求められ、xが確定するとyが確定しないとzとyが関係するので、時間は極値があり、極値を考えると3点で最適なyを求めるべきです.xに対しては,xを3点で解くと対応点のyの極値を出すことができ,チーム対応のyの極値を求めることができる.これで解けた.
コードは次のとおりです.

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
const double eps=1e-7;
const double ee=1e-9;
struct Point{
    double x,y;
};
double dis(Point a,Point b){
    return sqrt(ee+(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double q,p,r;
Point a,b,c,d,tmpx,tmpy;
double call(double t){
    tmpy.x=d.x+(c.x-d.x)/dis(c,d)*t*q;
    tmpy.y=d.y+(c.y-d.y)/dis(c,d)*t*q;
    return t+dis(tmpx,tmpy)/r;
}
double sanfen(double t){
    tmpx.x=a.x+(b.x-a.x)/dis(a,b)*t*p;
    tmpx.y=a.y+(b.y-a.y)/dis(a,b)*t*p;
    double low,high,mid,midd;
    low=0;
    high=dis(c,d)/q;
    while(high-low>eps){
        mid=(low+high)/2;
        midd=(mid+high)/2;
        if(call(mid)<call(midd))high=midd;
        else low=mid;
    }
    return t+call(mid);                                    
}                                      //   y 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
        scanf("%lf%lf%lf%lf",&c.x,&c.y,&d.x,&d.y);
        scanf("%lf%lf%lf",&p,&q,&r);
        double low,high,mid,midd;
        low=0;
        high=dis(a,b)/p;
        while(high-low>eps){
            mid=(low+high)/2;
            midd=(mid+high)/2;
            if(sanfen(mid)<sanfen(midd))high=midd;
            else low=mid;
        }                                   //   x  
        printf("%.2f
",sanfen(mid));
    }
    return 0;
}