QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#566964#9316. BoxesshiqiaqiayaAC ✓136ms4168kbC++173.8kb2024-09-16 04:19:532024-09-16 04:19:53

Judging History

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

  • [2024-09-16 04:19:53]
  • 评测
  • 测评结果:AC
  • 用时:136ms
  • 内存:4168kb
  • [2024-09-16 04:19:53]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>    // 包含 tree、gp_hash_table、cc_hash_table
#include <ext/pb_ds/priority_queue.hpp> // 引入后使用 STL 的堆需要 std::
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;
template<class key, class val = null_type, class cmp = less<>>
using rb_tree = tree<key, val, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class cmp = less<>>
using pairing_heap = __gnu_pbds::priority_queue<key, cmp>;
typedef long long ll;
#define int long long
mt19937_64 rd(time(0));

using type = int;
struct point : array<type, 3> {
    point operator * (const point & t) const { return {at(1) * t[2] - at(2) * t[1], at(2) * t[0] - at(0) * t[2], at(0) * t[1] - at(1) * t[0]}; }
    type operator / (const point & t) const { return at(0) * t[0] + at(1) * t[1] + at(2) * t[2]; }
    point & operator += (const point & t) { return at(0) += t[0], at(1) += t[1], at(2) += t[2], *this; }
    point operator + (const point & t) const { return point(*this) += t; }
    point & operator -= (const point & t) { return at(0) -= t[0], at(1) -= t[1], at(2) -= t[2], *this; }
    point operator - (const point & t) const { return point(*this) -= t; }
    point & operator *= (const type & t) { return at(0) *= t, at(1) *= t, at(2) *= t, *this; }
    point operator * (const type & t) const { return point(*this) *= t; }
    point & operator /= (const type & t) { return at(0) /= t, at(1) /= t, at(2) /= t, *this; }
    point operator / (const type & t) const { return point(*this) /= t; }

    void shake(double eps = 1e-10) {
        for (auto & t : *this) {
            t += ((double)rand() / RAND_MAX - 0.5) * eps;
        }
    }
};

struct face {
    array<int, 3> v;
    point norm;
};

vector<face> hull(vector<point> & q, vector<face> res = {}) {
    res.emplace_back(face{0, 1, 2, (q[1] - q[0]) * (q[2] - q[0])});
    res.emplace_back(face{2, 1, 0, (q[1] - q[2]) * (q[0] - q[2])});

    for (int i = 3; i < q.size(); i++) {
        vector<face> nf;
        set<array<int, 2>> edge;
        for (auto & x : res) {
            auto & [a, b, c] = x.v;
            if ((q[b] - q[a]) * (q[c] - q[a]) / (q[i] - q[a]) > 0) {
                edge.emplace(array<int, 2>{a, b});
                edge.emplace(array<int, 2>{b, c});
                edge.emplace(array<int, 2>{c, a});
            } else {
                nf.emplace_back(face{a, b, c, (q[b] - q[a]) * (q[c] - q[a])});
            }
        }
        for (auto & [x, y] : edge) {
            if (edge.count({y, x})) continue;
            nf.emplace_back(face{x, y, i, (q[y] - q[x]) * (q[i] - q[x])});
        }
        swap(res, nf);
    }
    return res;
}

void output(__int128 x) {
    if(x < 10) {
        cout << (int)x;
        return;
    }
    output(x / 10);
    cout << (int) (x % 10);
}

void QAQ() {
    int n;
    cin >> n;

    vector<point> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }

    __int128 ans = 0;

    while (a.size() > 3) {
        random_shuffle(a.begin(), a.end());
        vector<int> vis(a.size());
        auto res = hull(a);

        for (auto & x : res) {
            (ans += a[x.v[0]] * a[x.v[1]] / a[x.v[2]]);
            for (auto & idx : x.v) {
                vis[idx] = 1;
            }
        }

        vector<point> ta;
        for (int i = 0; i < a.size(); i++) {
            if (!vis[i]) {
                ta.push_back(a[i]);
            }
        }
        swap(a, ta);
    }

    output(ans);

    cout << "\n";
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    cout << fixed << setprecision(3);
    int t = 1;
    cin >> t;

    while (t--) {
        QAQ();
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3684kb

input:

2
4
0 0 1
0 0 2
0 1 1
1 1 1
10
2 6 3
2 9 0
2 1 0
3 7 3
0 5 6
10 9 2
4 4 2
8 5 2
4 6 9
6 7 5

output:

1
943

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 9ms
memory: 3692kb

input:

30
100
214848 13593 883915
404922 704679 762266
19696 348707 172137
204169 674312 980107
159743 683657 537795
913278 244484 331997
342255 150373 745862
822992 993127 812010
78019 523301 874868
508779 130959 577626
506563 15210 31018
302821 671498 135922
379735 258803 474373
387144 676958 499943
9009...

output:

8466306477510658674
7272556711339503943
7635348833914404146
8107228712222480162
8154398837331856360
7551703717471512369
8340343101157128252
7911868248459799324
7911957494280349996
8295429352750849603
8170150524727285883
7448641514858636645
8373196774630538132
7404986332777191754
7496214926512003280
...

result:

ok 30 lines

Test #3:

score: 0
Accepted
time: 3ms
memory: 3988kb

input:

300
10
284000 364959 249145
243447 261451 165064
884086 450907 263262
986606 115922 516435
550174 625062 491782
992985 764800 854837
992741 919628 758329
114851 373304 743149
236804 572126 522753
694056 863964 768484
10
328584 59621 865079
133943 928163 534857
746608 698892 195503
199343 568337 4820...

output:

803077918387863438
484728351097401010
1106436691630702280
544591678232219117
1068791025597242587
930320279051363466
977769839732812040
699051820151945692
1140525392772278038
1116781785107680980
844917700022644714
672066651386061967
638048751063849731
1258576451479348061
476673417837522259
8473170752...

result:

ok 300 lines

Test #4:

score: 0
Accepted
time: 76ms
memory: 3888kb

input:

1
3000
413652 522034 362874
161444 14592 423619
276585 592939 402025
969689 188554 136993
462321 11911 652603
155677 401331 635931
339965 202216 204346
992462 357822 565008
886658 168024 940016
767608 638795 810396
137017 720592 591380
131999 195424 726856
127795 754489 391676
201652 890036 283312
2...

output:

60273580163282897867

result:

ok single line: '60273580163282897867'

Test #5:

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

input:

3
1000
789847 633929 843311
151652 321247 368028
474261 971864 121395
276634 985203 701635
513707 455226 814706
268852 415657 58444
987338 896126 263240
299951 797298 467241
590635 66549 583890
167580 143498 207823
51652 874838 958088
384543 202601 354015
949301 50276 331784
786780 359270 507104
100...

output:

32630943894075643280
34329272009845651025
31688176605328214457

result:

ok 3 lines

Test #6:

score: 0
Accepted
time: 136ms
memory: 4100kb

input:

1
3000
523975 470644 532609
494477 538338 531617
478234 504027 544833
461636 519091 525762
465935 471859 476600
548753 495050 490073
472196 526755 531796
527926 514663 538795
487358 538942 471301
473223 533323 525932
529927 539631 505805
549573 493842 502137
451275 508234 507619
490260 486044 547014...

output:

13714262984719751837

result:

ok single line: '13714262984719751837'

Test #7:

score: 0
Accepted
time: 121ms
memory: 4168kb

input:

1
3000
501067 538720 531616
536331 513512 468418
481168 516601 456760
455909 516304 482968
470580 523520 467118
540251 523145 518549
529792 499609 540152
513977 547872 503582
451629 506750 510705
494903 528114 541031
536312 534273 502586
521942 525840 536753
505427 465349 535634
479677 462840 526571...

output:

26774763702823036290

result:

ok single line: '26774763702823036290'

Test #8:

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

input:

750
4
366621 367717 965717
877473 987234 992457
58094 519266 939201
626268 322233 986414
4
591196 179513 791976
612322 603915 878819
169697 463917 567056
768865 1872 876833
4
121807 839701 9401
198811 900500 901214
142256 317469 97653
217398 375325 967495
4
471186 234822 546514
176260 711278 268945
...

output:

7
3
6
1
6
6
60
1
14
2
1
36
1
2
16
16
3
22
15
2
4
12
4
7
3
9
92
5
4
12
5
21
4
8
36
2
5
3
4
20
5
4
22
1
6
17
2
9
92
1
8
25
8
1
6
3
3
2
20
14
2
4
4
3
6
5
8
3
26
2
4
10
9
3
9
11
5
10
2
1
3
4
5
2
7
2
3
14
3
1
5
9
6
10
4
14
2
108
10
4
1
8
6
2
6
10
2
1
2
18
4
4
6
55
10
2
8
2
2
9
4
10
63
22
12
6
4
2
5
4
3
3...

result:

ok 750 lines

Test #9:

score: 0
Accepted
time: 2ms
memory: 3716kb

input:

600
5
655543 510666 915704
380703 398956 256828
714237 871876 420340
195795 215699 17367
425447 771307 887138
5
285861 38399 167793
217868 63302 692533
369453 399834 394003
205960 213745 751859
522002 706659 22794
5
4827 310912 497102
635528 125551 962716
86160 372871 589378
365656 628248 460818
257...

output:

177136781473651118
20057408008635788
202167254547285205
91883626442191067
36098027134527379
256598264281323829
91762409777228118
289948413234149224
50961363019610796
68401673989921282
12031969509421726
283520264688323720
117934614795050966
266216543821792256
152304003128567987
180262487896919466
297...

result:

ok 600 lines

Extra Test:

score: 0
Extra Test Passed