M_sea

洛谷2571 [SCOI2010]传送带
Luogu算法三分套三分的板子?考虑固定点$E$,可以发现,此时的时间是关于$F$的单峰函数。证明不会然后再考虑动...
扫描右侧二维码阅读全文
02
2018/10

洛谷2571 [SCOI2010]传送带

Luogu

算法

三分套三分的板子?

考虑固定点$E$,可以发现,此时的时间是关于$F$的单峰函数。证明不会

然后再考虑动点$E$。可以发现,时间关于$E$也是一个单峰函数。

那么三分套三分即可。

代码重载了$Point$,所以很短。

代码

#include <bits/stdc++.h>
#define re register
#define EPS 1e-6
using namespace std;

inline double read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return (double)X*w;
}

struct Point {
    double x,y;
    Point(double _x=0,double _y=0) { x=_x,y=_y; }
    inline void get() { x=read(),y=read(); }
};

Point operator +(Point a,Point b) { return (Point){a.x+b.x,a.y+b.y}; }
Point operator *(Point a,int b) { return (Point){a.x*b,a.y*b}; }
Point operator /(Point a,int b) { return (Point){a.x/b,a.y/b}; }
inline double sqr(double a) { return a*a; }
inline double dis(Point a,Point b) { return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); }

Point A,B,C,D;
double p,q,r;

inline double calcCD(Point E) { //三分CD,得到EF+DF的最小值 
    Point L=C,R=D;
    while (fabs(L.x-R.x)>EPS||fabs(L.y-R.y)>EPS) {
        Point A1=(L+L+R)/3,A2=(L+R+R)/3;
        if (dis(E,A1)/r+dis(A1,D)/q<dis(E,A2)/r+dis(A2,D)/q) R=A2;
        else L=A1;
    }
    return dis(E,L)/r+dis(L,D)/q;
}

inline double calcAB() { //三分AB,得到AE+EF+DF的最小值 
    Point L=A,R=B;
    while (fabs(L.x-R.x)>EPS||fabs(L.y-R.y)>EPS) {
        Point A1=(L+L+R)/3,A2=(L+R+R)/3;
        if (dis(A,A1)/p+calcCD(A1)<dis(A,A2)/p+calcCD(A2)) R=A2;
        else L=A1;
    }
    return dis(A,L)/p+calcCD(L);
}

int main() {
    A.get(),B.get(),C.get(),D.get();
    p=read(),q=read(),r=read();
    printf("%.2f\n",calcAB());
    return 0;
}
最后修改:2019 年 05 月 26 日 03 : 02 PM

发表评论