「Bzoj 1857」「Scoi2010」传送带 (三分套三分)

BZOJ 1857
题意：见上。
观察(生活经验)发现，在 $ AB $ 上肯定存在一个点，他左移右移都会增大答案，所以是个单峰函数，同理 $ CD $ 。所以我们写一个三分套三分，即三分完以后再用这个三分结果进行下一个三分操作。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define LL long long
#define db double
#define ms(i, j) memset(i, j, sizeof i)

using namespace std;

namespace flyinthesky {

    const db eps = 1e-10;

    int ax, ay, bx, by, cx, cy, dx, dy, p, q, r;

    db dist(db xa, db ya, db xb, db yb) {return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));}
    db calc(db Ux, db Uy, db Dx, db Dy) {
        db U = dist(ax, ay, Ux, Uy) / (db)p;
        db D = dist(Dx, Dy, dx, dy) / (db)q;
        db H = dist(Ux, Uy, Dx, Dy) / (db)r;
        return U + D + H;
    }

    db f(db Ux, db Uy) {
        db lx_2 = cx, rx_2 = dx;
        db ly_2 = cy, ry_2 = dy;
        for (int i = 1; i <= 300; ++i) {
            db midx_2 = (lx_2 + rx_2) / 2.0;
            db midy_2 = (ly_2 + ry_2) / 2.0;
            db mmidx_2 = (midx_2 + rx_2) / 2.0;
            db mmidy_2 = (midy_2 + ry_2) / 2.0;
            if (calc(Ux, Uy, midx_2, midy_2) - calc(Ux, Uy, mmidx_2, mmidy_2) > eps) lx_2 = midx_2, ly_2 = midy_2;
            else rx_2 = mmidx_2, ry_2 = mmidy_2;
        }
        return calc(Ux, Uy, lx_2, ly_2);
    }

    void clean() {
    }
    int solve() {
        scanf("%d%d%d%d%d%d%d%d%d%d%d", &ax, &ay, &bx, &by, &cx, &cy, &dx, &dy, &p, &q, &r);
        clean();
        db lx_1 = ax, rx_1 = bx;
        db ly_1 = ay, ry_1 = by;
        for (int i = 1; i <= 300; ++i) {
            db midx_1 = (lx_1 + rx_1) / 2.0;
            db midy_1 = (ly_1 + ry_1) / 2.0;
            db mmidx_1 = (midx_1 + rx_1) / 2.0;
            db mmidy_1 = (midy_1 + ry_1) / 2.0;
            if (f(midx_1, midy_1) - f(mmidx_1, mmidy_1) > eps) lx_1 = midx_1, ly_1 = midy_1;
            else rx_1 = mmidx_1, ry_1 = mmidy_1;
        }
        printf("%.2f\n", f(lx_1, ly_1));
        return 0;
    }
};
int main() {
    flyinthesky::solve();
    return 0;
}