QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#464480#8214. Huge Oil Platformucup-team3215WA 1ms3920kbC++234.3kb2024-07-06 09:57:132024-07-06 09:57:13

Judging History

你现在查看的是最新测评结果

  • [2024-07-06 09:57:13]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3920kb
  • [2024-07-06 09:57:13]
  • 提交

answer

#include <bits/stdc++.h>


using namespace std;
using ll = long long;
using ld = double;


template<class T>
int sgn(T x) { return (x > 0) - (x < 0); }

template<class T>
struct Point {
    typedef Point P;
    T x, y;

    explicit Point(T x = 0, T y = 0) : x(x), y(y) {}

    template<typename U>
    explicit Point(Point<U> o) : x(o.x), y(o.y) {};

    bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }

    bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }

    P operator+(P p) const { return P(x + p.x, y + p.y); }

    P operator-(P p) const { return P(x - p.x, y - p.y); }

    P operator*(T d) const { return P(x * d, y * d); }

    P operator/(T d) const { return P(x / d, y / d); }

    T dot(P p) const { return x * p.x + y * p.y; }

    T cross(P p) const { return x * p.y - y * p.x; }

    T cross(P a, P b) const { return (a - *this).cross(b - *this); }

    T dist2() const { return x * x + y * y; }

    ld dist() const { return sqrtl(dist2()); }

    P unit() const { return *this / dist(); } // makes dist()=1
    P perp() const { return P(-y, x); } // rotates +90 degrees

    // returns point rotated 'a' radians ccw around the origin
    P rotate(double a) const {
        return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    friend ostream &operator<<(ostream &os, P p) {
        return os << "(" << p.x << "," << p.y << ")";
    }
};

struct s_tr {
    const vector<pair<ld, int>> &all;
    vector<array<ld, 6>> s;

    s_tr(const vector<pair<ld, int>> &all) : all(all) {
        ll n = all.size();
        s.resize(4 * n, array<ld, 6>{});
    }

    auto combine(const array<ld, 6> &lhs, const array<ld, 6> &rhs) {
        array<ld, 6> res{};
        res[3] = rhs[3] + lhs[3];
        res[2] = max(rhs[2], rhs[3] + lhs[2]);
        res[1] = max(lhs[1], lhs[3] + rhs[1]);
        res[4] = max(lhs[4], lhs[3] + rhs[4]);
        res[5] = max(rhs[5], rhs[3] + lhs[5]);
        res[0] = max({lhs[0], rhs[0], rhs[4] + lhs[5]});
        return res;
    }

    void upd(int v, int l, int r, int k, ld val) {
        if (l + 1 == r) {
            s[v][3] = s[v][2] = s[v][1] = s[v][0] = val;
            s[v][4] = val - 2 * all[l].first;
            s[v][5] = val + 2 * all[l].first;
            return;
        }
        int m = (r + l) / 2;
        if (k < m)upd(v * 2 + 1, l, m, k, val);
        else upd(v * 2 + 2, m, r, k, val);
        s[v] = combine(s[v * 2 + 1], s[v * 2 + 2]);
    }

};

template<typename P>
P lineProj(P a, P b, P p, bool refl = false) {
    P v = b - a;
    return p - v.perp() * (1 + refl) * v.cross(p - a) / v.dist2();
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<Point<ll>> a(n);
    vector<ll> w(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].x >> a[i].y >> w[i];
    }
    ld res{0};
    for (int i = 0; i < n; ++i) {
        auto v = a;
        for (auto &x: v)x = x - a[i];
        Point<ld> A(v[i]);
        for (int j = i + 1; j < n; ++j) {
            Point<ld> B(v[j]);
            auto solve = [&](bool inv) {
                vector<pair<ld, ll>> points;
                vector<pair<ld, int>> all;
                for (int k = 0; k < n; ++k) {
                    Point<ld> C(v[k]);
                    if ((inv ? -1 : 1) * v[j].cross(v[k]) >= 0) {
                        auto z = lineProj(A, B, C);
                        all.emplace_back(z.dist() * ((v[j]).dot(v[k]) < 0 ? -1 : 1), k);
                        points.push_back({(z - C).dist(), k});
                    }
                }
                sort(all.begin(), all.end());
                vector<int> pos(n);
                for (int j = 0; j < all.size(); ++j) {
                    pos[all[j].second] = j;
                }
                sort(points.begin(), points.end());
                int N = all.size();
                s_tr tree(all);
                for (auto [d, k]: points) {
                    int p = pos[k];
                    tree.upd(0, 0, N, p, w[k]);
                    res = max(res, -2 * d + tree.s[0][0]);
                }
            };
            solve(false);
            solve(true);
        }
    }
    cout << fixed << setprecision(20);
    cout << res;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3920kb

input:

2
1 1 1
3 3 1

output:

1.00000000000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

3
4 5 5
4 6 7
1 3 8

output:

10.10050506338833464781

result:

ok found '10.1005051', expected '10.1005051', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

2
0 0 1
1000000 1000000 1000000000

output:

1000000000.00000000000000000000

result:

ok found '1000000000.0000000', expected '1000000000.0000000', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3872kb

input:

20
328 207 21
365 145 188
347 79 41
374 335 699
288 250 97
32 267 131
296 332 434
2 91 36
139 43 21
26 455 696
57 135 410
14 500 396
255 181 646
103 114 593
309 351 787
207 316 138
440 416 806
413 349 695
413 201 501
455 396 442

output:

6507.62850931608045357279

result:

wrong answer 1st numbers differ - expected: '6092.4427126', found: '6507.6285093', error = '0.0681477'