BZOJ 1857 [Scoi2010]传送带 三分套三分

题意: 在AB上走的速度是P，在CD上走的速度是Q，在平面走的速度是R，现在询问从A走到D最少花费多长时间。 解析: 模型挺好想？ 先查找出来在AB上走到哪比较好，找这个的同时需要再套一个查找找在CD上走到哪好。 但是二分为什么不行？ 因为如果我们是二分的话，我们找到一个点后，没有根据使得我们可以向左分或者是向右分，，但是这个题来说，假设找到两个点A,B如果走A比走B优的话那么答案一定在AB之间，（据说是物理问题不要问我） 所以我们可以三分出来两个三等分点，然后比较一下再决定向哪边分。 代码:

;double P,Q,R;struct Point{double x,y;Point(){}Point(double _x,double _y):x(_x),y(_y){}friend istream& operator >> (istream &_,Point &a){scanf(“%lf%lf”,&a.x,&a.y);return _;}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);}Point operator * (double rate){return Point(x*rate,y*rate);}double operator * (const Point &a){return x*a.x+y*a.y;}double operator ^ (const Point &a){return x*a.y-y*a.x;}friend double get_dis(Point a,Point b){return sqrt((a-b)*(a-b));}}A,B,C,D;double calc(Point a){Point l(C.x,C.y),r(D.x,D.y);while(fabs(r.x-l.x)>eps||fabs(r.y-l.y)>eps){Point tri1=l+(r-l)*(1.0/3);Point tri2=l+(r-l)*(2.0/3);double cost1=get_dis(A,a)/P+get_dis(a,tri1)/R+get_dis(tri1,D)/Q;double cost2=get_dis(A,a)/P+get_dis(a,tri2)/R+get_dis(tri2,D)/Q;if(cost1>cost2)l=tri1;else r=tri2;}return get_dis(A,a)/P+get_dis(a,l)/R+get_dis(l,D)/Q;}int main(){cin>>A>>B>>C>>D;scanf(“%lf%lf%lf”,&P,&Q,&R);Point l(A.x,A.y);Point r(B.x,B.y);while(fabs(r.x-l.x)>eps||fabs(r.y-l.y)>eps){Point tri1=l+(r-l)*(1.0/3);Point tri2=l+(r-l)*(2.0/3);double cost1=calc(tri1);double cost2=calc(tri2);if(cost1>cost2)l=tri1;else r=tri2;}printf(“%.2lf\n”,calc(l));}

发光并非太阳的专利，你也可以发光