SGU278 【Fuel】题解

 latex粘上来有些问题，就直接传截图算了

latex源码自取：

我们用 $x_i$ 表示 $c_ix_i$ , $d_i$ 表示 $\frac{a_i}{c_i}$ ， $e_i$ 表示 $\frac{b_i}{c_i}$ ， 那么题意就可以转化为 $\sum d_ix_i \leq A$ ， $\sum e_ix_i \leq B$ ， 求$\max\{\sum x_i\}$ 。

 

对于这些式子，可以接着化为 $\bar dx \leq A$ ， $\bar ex \leq B$ ，求 $\max\{x\}$ ，也就是求 $\max\{\min\{\frac{A}{\bar d}, \frac{B}{\bar e}\}\}$ 。

 

我们将每种燃料看作一个点 $(d_i, e_i)$ ，那么最终能表示的 $(\bar d, \bar e)$ 也就在 $(d_i, e_i)$ 所组成的凸包的范围内（两个向量的情况是文化课内容，然后拓展一下就行（逃））。

 

根据 $ans=\max\{\min\{\frac{A}{\bar d}, \frac{B}{\bar e}\}\}$ 瞎推一下可以发现在这个凸包中，在直线 $y=\frac{B}{A}x$ 上的凸包中，答案最大的点是 $\bar e$ 最小的点，而在直现 $y=\frac{B}{A}$ 下的凸包中，答案最大的点是 $\bar d$ 最小的点，在直线 $y=\frac{B}{A}$ 上的凸包中，答案最大的则是离原点最近的点。

 

最后再瞎推一下，这些点显然在凸包的端点或者凸包和直线 $y=\frac{B}{A}$ 的交点上，所以针对这些点求答案即可。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const double eps = 1e-8;

int n, id, top, A, B;

int a[75005], b[75005], c[75005];

double ans;

struct point

{

    double x;

    double y;

    point(double aa = 0, double bb = 0)

    {

        x = aa;

        y = bb;

    }

    point operator+(const point &bb) const

    {

        return point(x + bb.x, y + bb.y);

    }

    point operator-(const point &bb) const

    {

        return point(x - bb.x, y - bb.y);

    }

    double operator*(const point &bb) const

    {

        return x * bb.x + y * bb.y;

    }

    double operator^(const point &bb) const

    {

        return x * bb.y - y * bb.x;

    }

    double dis(point bb)

    {

        return sqrt((x - bb.x) * (x - bb.x) + (y - bb.y) * (y - bb.y));

    }

} minx, p[75005], st[75005];

struct line

{

    point a;

    point b;

    line() {}

    line(point aa, point bb)

    {

        a = aa;

        b = bb - aa;

    }

};

point intersect(line aa, line bb)

{

    point cc = aa.a - bb.a;

    double k = (bb.b ^ cc) / (aa.b ^ bb.b);

    cc = point(aa.b.x * k, aa.b.y * k);

    return aa.a + cc;

}

bool cmp(point aa, point bb)

{

    if (abs((aa - p[1]) ^ (bb - p[1])) <= eps)

        return aa.dis(p[1]) < bb.dis(p[1]);

    return ((aa - p[1]) ^ (bb - p[1])) > 0;

}

int main()

{

    scanf("%d%d%d", &n, &A, &B);

    for (int i = 1; i <= n; ++i)

    {

        scanf("%d%d%d", &a[i], &b[i], &c[i]);

        p[i].x = (double)a[i] / c[i];

        p[i].y = (double)b[i] / c[i];

    }

    id = 1;

    minx = p[1];

    for (int i = 2; i <= n; ++i)

        if (minx.y - p[i].y > eps || (fabs(p[i].y - minx.y) <= eps && minx.x - p[i].x > eps))

        {

            id = i;

            minx = p[i];

        }

    swap(p[1], p[id]);

    sort(p + 2, p + n + 1, cmp);

    for (int i = 1; i <= n; ++i)

    {

        while (top >= 2 && ((p[i] - st[top - 1]) ^ (st[top] - st[top - 1])) > -eps)

            --top;

        st[++top] = p[i];

    }

    for (int i = 1; i <= top; ++i)

        ans = max(ans, min(A / st[i].x, B / st[i].y));

    st[top + 1] = st[1];

    for (int i = 1; i <= top; ++i)

    {

        point vec = intersect(line(st[i], st[i + 1]), line(point(0, 0), point(A, B)));

        if (vec.x - min(st[i].x, st[i + 1].x) > -eps && vec.x - max(st[i].x, st[i + 1].x) < eps)

            if (vec.y - min(st[i].y, st[i + 1].y) > -eps && vec.y - max(st[i].y, st[i + 1].y) < eps)

                ans = max(ans, A / vec.x);

    }

    printf("%.6f", ans);

    return 0;

}