QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#464463#8214. Huge Oil Platformucup-team3215TL 1ms4012kbC++234.4kb2024-07-06 09:00:412024-07-06 09:00:42

Judging History

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

  • [2024-07-06 09:00:42]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4012kb
  • [2024-07-06 09:00:41]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long 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, 4>> s;

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

    ld len(int pos) {
        assert(pos);
        return all[pos].first - all[pos - 1].first;
    }

    auto combine(const array<ld, 4> &lhs, const array<ld, 4> &rhs, int m) {
        array<ld, 4> res{};
        ld l = -2 * len(m);
        res[3] = rhs[3] + lhs[3] + l;
        res[2] = max(rhs[2], rhs[3] + lhs[2] + l);
        res[1] = max(lhs[1], lhs[3] + rhs[1] + l);
        res[0] = max({lhs[0], rhs[0], l + rhs[1] + lhs[2]});
        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;
            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], m);
    }

};

Point<ld> lineProj(Point<ll> a, Point<ll> b, Point<ll> p) {
    auto v = b - a;
    return Point<ld>(p) - Point<ld>(v.perp()) * (v.cross(p - a) / (ld) v.dist2());
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    mt19937 rng{1000 - 7};
    int n = 400;
    cin >> n;
    vector<Point<ll>> a(n);
    vector<ll> w(n);
    for (int i = 0; i < n; ++i) {
        a[i].x = rng() % (int) 1e6;
        a[i].y = rng() % (int) 1e6;
        w[i] = rng() % (int) 1e9;
        cin >> a[i].x >> a[i].y >> w[i];
    }
    ld res{0};
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            Point<ld> A(a[i]);
            Point<ld> B(a[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(a[k]);
                    if ((inv ? -1 : 1) * (a[j] - a[i]).cross(a[k] - a[i]) >= 0) {
                        auto z = lineProj(a[i], a[j], a[k]);
                        all.emplace_back((z - A).dist() * ((a[j] - a[i]).dot(a[k] - a[i]) < 0 ? -1 : 1), k);
                        points.emplace_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: 3900kb

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: 3940kb

input:

3
4 5 5
4 6 7
1 3 8

output:

10.10050506338833465822

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: 0
Accepted
time: 0ms
memory: 3796kb

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:

6092.44271262378278919414

result:

ok found '6092.4427126', expected '6092.4427126', error '0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3884kb

input:

20
38 207 766
202 485 964
257 466 900
205 486 738
166 53 716
61 94 881
252 165 182
63 292 612
225 278 242
224 242 566
381 196 702
56 494 997
268 288 884
379 227 3
357 271 975
55 73 678
260 55 623
399 369 515
116 354 580
404 239 950

output:

11878.25731282745992789529

result:

ok found '11878.2573128', expected '11878.2573128', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3844kb

input:

20
249 215 320
38 48 229
457 366 56
36 142 186
44 96 935
97 190 143
215 218 123
116 486 291
304 232 463
429 297 29
479 475 97
97 198 405
69 395 121
381 121 926
137 197 972
410 91 218
87 421 737
117 390 144
319 287 170
353 302 754

output:

5573.25589693263021695557

result:

ok found '5573.2558969', expected '5573.2558969', error '0.0000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 4012kb

input:

20
474 215 66
376 120 6
367 259 211
362 293 34
416 407 554
133 292 894
171 278 871
459 187 674
383 192 980
352 78 899
83 27 684
138 185 709
357 234 359
390 241 40
418 124 161
258 348 462
408 59 851
110 184 668
28 447 761
20 131 367

output:

8510.59561788340911370199

result:

ok found '8510.5956179', expected '8510.5956179', error '0.0000000'

Test #8:

score: -100
Time Limit Exceeded

input:

400
979422 264252 76260
922920 334464 58710
87057 798078 39652
602478 649867 49073
388746 161788 44501
727471 373113 28061
944959 505744 22145
191465 164645 49421
102241 771049 65953
44911 762286 34082
112779 537040 98117
688054 585935 53647
391845 931395 55355
788464 698271 91449
984533 409449 8331...

output:


result: