QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#464471#8214. Huge Oil Platformucup-team3215WA 7951ms4400kbC++234.5kb2024-07-06 09:21:212024-07-06 09:21:21

Judging History

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

  • [2024-07-06 09:21:21]
  • 评测
  • 测评结果:WA
  • 用时:7951ms
  • 内存:4400kb
  • [2024-07-06 09:21:21]
  • 提交

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 << ")";
    }
};

constexpr ld INF = 1e14 + 123;

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) {
        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);
    }

};

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);
    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};
    vector<pair<int, int>> rofl;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j)rofl.emplace_back(i, j);
    }
    shuffle(rofl.begin(), rofl.end(), rng);
    while ((ld) clock() / CLOCKS_PER_SEC < 7.95 && rofl.size()) {
        auto [i, j] = rofl.back();
        rofl.pop_back();
        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, B, C);
                    all.emplace_back((z - A).dist() * ((a[j] - a[i]).dot(a[k] - a[i]) < 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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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: 2ms
memory: 3924kb

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

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

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

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

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:

35610300.74428987376086297445

result:

ok found '35610300.7442899', expected '35610300.7442899', error '0.0000000'

Test #9:

score: 0
Accepted
time: 7935ms
memory: 4156kb

input:

400
972392 809281 95619
19054 872671 65516
732236 376176 38922
412232 147107 36902
242843 486112 34287
311141 416172 5612
453695 775962 79060
806457 678364 29585
324358 953486 58858
532543 378842 67089
20301 449627 86941
252735 242252 66239
335667 454693 40007
563783 444579 49920
663605 128448 3095
...

output:

35334006.33097682120933313854

result:

ok found '35334006.3309768', expected '35334006.3309768', error '0.0000000'

Test #10:

score: 0
Accepted
time: 7943ms
memory: 4248kb

input:

400
718289 727141 23905
849810 500522 44241
890554 385825 70996
597411 423432 99133
994251 463004 32770
388843 280170 47562
664865 319482 48403
353770 474376 52218
508270 890719 28901
80661 697191 77469
459811 411012 23750
741501 408373 60551
163462 269625 56148
406785 260156 41900
337932 855364 578...

output:

36725958.76718687036554911174

result:

ok found '36725958.7671869', expected '36725958.7671869', error '0.0000000'

Test #11:

score: 0
Accepted
time: 7951ms
memory: 4092kb

input:

400
6840 184362 43862
608935 154893 10000000
746897 683314 71237
255918 899062 94342
478185 102216 1923
890855 323689 44654
467417 577805 20
919997 267591 21891
303668 171438 29365
324647 818449 18945
229942 874921 22870
174645 613823 31193
559386 859851 36262
156698 936021 86194
968031 522125 75799...

output:

36590958.86049337056829244830

result:

ok found '36590958.8604934', expected '36590958.8604934', error '0.0000000'

Test #12:

score: 0
Accepted
time: 7940ms
memory: 4400kb

input:

400
213928 419916 45837
334919 278535 7824
100882 416988 26147
682280 524709 85794
569137 589867 48913
344075 156956 4813
87794 655931 25690
285467 798402 55113
295984 894760 44628
535011 461670 72400
917862 461662 90830
544780 751382 81071
588022 966874 10000000
872058 880760 39315
216881 626161 22...

output:

46173511.87199231090926332399

result:

ok found '46173511.8719923', expected '46173511.8719923', error '0.0000000'

Test #13:

score: 0
Accepted
time: 7947ms
memory: 4180kb

input:

400
937407 829281 77362
837708 843713 34574
77624 684540 68232
786430 452449 38426
486327 341660 86859
964636 122535 12764
699975 284575 84208
806142 721010 10955
464680 787842 37887
395874 727033 70790
59849 84503 90263
557124 876914 45080
168385 390089 16463
6894 13302 8291
380410 621577 47431
992...

output:

45704049.96153425236843759194

result:

ok found '45704049.9615343', expected '45704049.9615343', error '0.0000000'

Test #14:

score: 0
Accepted
time: 7944ms
memory: 4160kb

input:

400
769436 473525 91179
925212 211008 73863
393798 496395 71452
241696 745916 92387
519975 24414 32489
867615 821099 81949
644522 605802 2383
237926 379309 38924
389221 50127 90627
201042 315597 28025
314735 422671 18588
616409 476289 21284
397182 521279 80524
190834 918992 35979
405770 829871 41232...

output:

46077961.21213435679965186864

result:

ok found '46077961.2121344', expected '46077961.2121344', error '0.0000000'

Test #15:

score: -100
Wrong Answer
time: 7940ms
memory: 4208kb

input:

400
661885 939867 75528
487494 846559 71593
290098 369543 36755
931898 794760 63921
480058 761470 19842
426135 379317 3551
627245 832185 26033
598705 59485 2540
941138 844706 6210
377586 312034 96388
398374 295001 41568
874081 558382 41501
933464 285407 30933
444410 590787 18450
950252 399446 44906
...

output:

45281605.93640943580612656660

result:

wrong answer 1st numbers differ - expected: '45282826.9191970', found: '45281605.9364094', error = '0.0000270'