BZOJ1857 SCOI2010 传送带 (三分)

经典的三分问题。

一看到这道题好懵啊，无用地想了一会果断看题解，发现要用到三分，于是赶紧去补了补课...

题目大意是这样的：两条线段AB和CD在一个平面中，分别给出在AB，CD，和平面上的速度，要我们从A到D的最短时间。

因为有两条线段，我们可以三分套三分，先对AB三分，找到AB上的最优点x，在x确定的基础上，对CD进行三分，找到最优点y，x和y都确定了，答案也就有了、

#include
using namespace std;
#define eps 1e-8
struct Point{//计算几何定义结构体 double x,y;Point(){};Point(double xx,double yy):x(xx),y(yy){};Point operator / (double a){return Point(x/a,y/a);}Point operator - (const Point &a){return Point(x-a.x,y-a.y);}Point operator + (const Point &a){return Point(x+a.x,y+a.y);}
}A,B,C,D;
double P,Q,R;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 calc(Point X){//在X固定时，找CD上的最优点 Point l=C,r=D;while(dis(l,r)>eps){Point x=(r-l)/3;Point lmid=l+x,rmid=r-x;double ans1=dis(lmid,D)/Q+dis(X,lmid)/R;double ans2=dis(rmid,D)/Q+dis(X,rmid)/R;if(ans2-ans1>eps) r=rmid;else l=lmid;}return dis(l,D)/Q+dis(X,l)/R;
}double Solve(){//找AB上的最优点X Point l=A,r=B;while(dis(l,r)>eps){Point x=(r-l)/3;Point lmid=l+x,rmid=r-x;//两个三分点double ans1=calc(lmid)+dis(lmid,A)/P;double ans2=calc(rmid)+dis(rmid,A)/P;if(ans2-ans1>eps) r=rmid;else l=lmid;//单峰函数是下凸的 }return calc(l)+dis(l,A)/P;//最优解(答案) 
}int main(){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);printf("%0.2lf",Solve()); return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！