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 nidtopAB;
int a[75005], b[75005], c[75005];
double ans;
struct point
{
    double x;
    double y;
    point(double aa = 0double bb = 0)
    {
        x = aa;
        y = bb;
    }
    point operator+(const point &bbconst
    {
        return point(x + bb.xy + bb.y);
    }
    point operator-(const point &bbconst
    {
        return point(x - bb.xy - bb.y);
    }
    double operator*(const point &bbconst
    {
        return x * bb.x + y * bb.y;
    }
    double operator^(const point &bbconst
    {
        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));
    }
minxp[75005], st[75005];
struct line
{
    point a;
    point b;
    line() {}
    line(point aapoint bb)
    {
        a = aa;
        b = bb - aa;
    }
};
point intersect(line aaline bb)
{
    point cc = aa.a - bb.a;
    double k = (bb.b ^ cc) / (aa.b ^ bb.b);
    cc = point(aa.b.x * kaa.b.y * k);
    return aa.a + cc;
}
bool cmp(point aapoint 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 = 1i <= 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 = 2i <= 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 + 2p + n + 1cmp);
    for (int i = 1i <= n; ++i)
    {
        while (top >= 2 && ((p[i- st[top - 1]) ^ (st[top- st[top - 1])) > -eps)
            --top;
        st[++top= p[i];
    }
    for (int i = 1i <= top; ++i)
        ans = max(ansmin(A / st[i].xB / st[i].y));
    st[top + 1= st[1];
    for (int i = 1i <= top; ++i)
    {
        point vec = intersect(line(st[i], st[i + 1]), line(point(00), point(AB)));
        if (vec.x - min(st[i].xst[i + 1].x) > -eps && vec.x - max(st[i].xst[i + 1].x) < eps)
            if (vec.y - min(st[i].yst[i + 1].y) > -eps && vec.y - max(st[i].yst[i + 1].y) < eps)
                ans = max(ansA / vec.x);
    }
    printf("%.6f"ans);
    return 0;
}

评论

发表评论