题解 | #北京信息科技大学第十五届程序设计竞赛（同步赛）#

Link

G

从散点中求凸包，再枚举每条线，求离该线距离最远的凸包的顶点。

。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
using Point = complex<i64>;

auto cross(const Point &a, const Point &b) { 
    return imag(conj(a) * b); 
}

struct Line {
    Point a, b;
    Line() = default;
    Line(const Point &a, const Point &b) : a(a), b(b) {}
};

auto onLeft(const Point &p, const Line &l) { 
    return cross(l.b - l.a, p - l.a); 
}

template <typename F> 
int extreme(const F &dir, const vector<Point> &p) {
    int N = p.size();
    const auto check = [&](const int i) {
        return onLeft(p[(i + 1) % N], Line(p[i], dir(p[i]) + p[i])) >= 0;
    };
    const auto dir0 = dir(p[0]);
    const auto check0 = check(0);
    if (!check0 && check((int) p.size() - 1)) {
        return 0;
    }
    const auto cmp = [&](const Point &v) {
        const int vi = &v - p.data();
        if (vi == 0) {
            return 1;
        }
        const auto checkv = check(vi);
        const auto t = onLeft(v, Line(p[0], dir(p[0]) + p[0]));
        if (vi == 1 && checkv == check0 && t == 0) {
            return 1;
        }
        return checkv ^ (checkv == check0 && t <= 0);
    };
    return partition_point(p.begin(), p.end(), cmp) - p.begin();
}

pair<int, int> tangent(const Line &a, const vector<Point> &p) {
    const int i = extreme([&](...) { return +(a.b - a.a); }, p);
    const int j = extreme([&](...) { return -(a.b - a.a); }, p);
    return {i, j};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<Point> a(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = Point(x, y);
    }

    sort(a.begin(), a.end(), [&](auto a, auto b) {
        if (real(a) != real(b)) {
            return real(a) < real(b);
        }
        return imag(a) < imag(b);
    });

    vector<Point> p;
    for (int i = 0; i < n; i++) {
        while (p.size() > 1 && cross(p[(int) p.size() - 1] - p[(int) p.size() - 2], a[i] - p[(int) p.size() - 2]) <= 0) {
            p.pop_back();
        }
        p.push_back(a[i]);
    }
    
    int k = p.size();
    for (int i = n - 2; i >= 0; i--) {
        while (p.size() > k && cross(p[(int) p.size() - 1] - p[(int) p.size() - 2], a[i] - p[(int) p.size() - 2]) <= 0) {
            p.pop_back();
        }
        p.push_back(a[i]);
    }
    p.pop_back();

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        Line L(Point(0, 0), a[i]);
        auto &[x, y] = tangent(L, p);
        ans = max(ans, abs(cross(p[x], a[i])));
        ans = max(ans, abs(cross(p[y], a[i])));
    }
    cout << fixed << setprecision(10) << 1.0 * ans / 2.0;

    return 0;
}

I

。

。

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

template <class T>
T exgcd(T a, T b, T &x, T &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    T g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, p, q, k;
    cin >> n >> p >> q >> k;

    vector<int> cost(n), w(n);
    for (int i = 0; i < n; i++) {
        int pos, like, l, r;
        cin >> pos >> like >> w[i] >> l >> r;

        int res = 2E9;
        for (int k2 = 0; k2 <= k / q; k2++) {
            int C = pos + k2 * r;
            int k1, k3;
            int g = exgcd(l, like, k1, k3);
            if (C % g) {
                continue;
            }
            int a = l / g, b = like / g, x = C / g;
            k1 = (k1 * x % b + b) % b;
            res = min(res, k1 * p + k2 * q);
        }
        cost[i] = res;
    }

    vector<int> f(k + 1);
    for (int i = 0; i < n; i++) {
        for (int j = k; j >= cost[i]; j--) {
            f[j] = max(f[j], f[j - cost[i]] + w[i]);
        }
    }
    cout << f[k] << '\n';

    return 0;
}