bzoj1857 [ SCOI2010 ],bzoj1857scoi2010

显著大家必定是先走到AB上一点X,然后走到CD上一点Y,最终到D。

那就是说答案就是|AX|/P+|XY|/奔驰M级+|YD|/Q

倘诺我们早已规定了X,那么目的正是在CD上找一点Y,使|XY|/LX570+|YD|/Q最小。

闻名海外这是个单峰函数。

那么柒分套七分就足以了。

 

代码:

永利皇宫 1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define Eps 1e-3
struct Node{
    double x,y;
    Node(){}
    Node(double x,double y):x(x),y(y){}
    Node operator + (Node a){return Node(x+a.x,y+a.y);}
    Node operator - (Node a){return Node(x-a.x,y-a.y);}
    Node operator / (double a){return Node(x/a,y/a);}
    inline void Read(){scanf("%lf%lf",&x,&y);}
}a,b,c,d,l,r,m1,m2;
int i,j,k,n,m,p,v1,v2,v3;
inline double Dis(Node a,Node b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline double Get(Node a,Node b,Node c,Node d){
    return Dis(a,b)/v1+Dis(b,c)/v3+Dis(c,d)/v2;
}
inline double Calc(Node x){
    Node l=c,r=d,m1,m2;
    while(Dis(l,r)>Eps){
        m1=(r-l)/3;m2=r-m1;m1=l+m1;
        if(Get(a,x,m1,d)>Get(a,x,m2,d))l=m1;else r=m2;
    }
    return Get(a,x,l,d);
}
int main(){
    a.Read();b.Read();c.Read();d.Read();
    scanf("%d%d%d",&v1,&v2,&v3);
    l=a;r=b;
    while(Dis(l,r)>Eps){
        m1=(r-l)/3;m2=r-m1;m1=l+m1;
        if(Calc(m1)>Calc(m2))l=m1;else r=m2;
    }
    printf("%.2lf\n",Calc(l));
    return 0;
}

bzoj1857

 

[永利皇宫 , SCOI2010 ],bzoj1857scoi二〇〇九明显大家终将是先走到AB上一点X,然后走到CD上一点Y,最后到D。
那么答案正是|AX|/P+|XY|/卡宴+|YD|/Q 假若大家早就…

明明大家一定是先走到AB上一点X,然后走到CD上一点Y,最后到D。

那正是说答案正是|AX|/P+|XY|/奥迪Q5+|YD|/Q

假诺大家已经规定了X,那么指标就是在CD上找一点Y,使|XY|/冠道+|YD|/Q最小。

家谕户晓那是个单峰函数。

那就是说九分套七分就能够了。

 

网站地图xml地图