QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#566964 | #9316. Boxes | shiqiaqiaya | AC ✓ | 136ms | 4168kb | C++17 | 3.8kb | 2024-09-16 04:19:53 | 2024-09-16 04:19:53 |
Judging History
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