BZOJ 1857 [Scoi2010]传送带三分

2019-11-06 09:13:12

字体：大中小

来源：转载

供稿：网友

题目大意：在一个2维平面上有两条线段，分别为线段AB和线段CD。在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在想从A点走到D点，最少需要走多长时间

根据常识一定是在分别在传送带上走一段，在平地上走一段。

答案关于在两条传送带上走的距离是单峰的（具体证明）然后三分搞一搞就好了

#include <cstdio>#include <cmath>#include <algorithm>using namespace std;inline double sq(double x) {return x*x;} ///squarestruct Point { double x,y; Point(double _x=0,double _y=0):x(_x),y(_y) {} void scan() {scanf("%lf%lf",&x,&y);} double Operator ^ (const Point& rhs) const {return sqrt(sq(rhs.x-x)+sq(rhs.y-y));} /// calculate distance Point operator - (const Point& rhs) const {return Point(x-rhs.x,y-rhs.y);} Point operator + (const Point& rhs) const {return Point(x+rhs.x,y+rhs.y);} Point operator / (const double& rhs) const {return Point(x/rhs,y/rhs);}}a[2],b[2],O[2];double p,q,r;const double eps=1e-12;double getA() {return (a[0]^O[0])/p+(O[0]^O[1])/r+(O[1]^b[1])/q;}double Trisection(int x) { Point l=a[x],r=b[x],mid[2],tmp; double A[2],cur; while((l^r)>eps) { tmp=(r-l)/3; mid[0]=l+tmp, mid[1]=r-tmp; O[x]=mid[0]; A[0]=(x ? Trisection(0) : getA()); O[x]=mid[1]; A[1]=(x ? Trisection(0) : getA()); if(A[0] < A[1]) r=mid[1]; else l=mid[0]; } if((a[x]^b[x])<=eps) O[x]=a[x], cur=(x ? Trisection(0) : getA()); else cur=A[0]; return cur;}int main() { for(int i=0;i<2;i++) a[i].scan(), b[i].scan(); scanf("%lf%lf%lf",&p,&q,&r); PRintf("%.2f/n",Trisection(1)); return 0;}

上一篇：日语实用生活词汇系列——理发用语篇「髪を切る」

下一篇：从华为清理34岁以上老员工想起的二三事