QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#567080 | #9316. Boxes | shiqiaqiaya | WA | 1ms | 3652kb | C++17 | 4.0kb | 2024-09-16 06:20:53 | 2024-09-16 06:20:54 |
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));
template <class type>
struct point : array<type, 3> {
using p = array<type, 3>;
type operator / (const point & t) const { return p::at(0) * t[0] + p::at(1) * t[1] + p::at(2) * t[2]; }
point operator * (const point & t) const { return {p::at(1) * t[2] - p::at(2) * t[1], p::at(2) * t[0] - p::at(0) * t[2], p::at(0) * t[1] - p::at(1) * t[0]}; }
point operator + (const point & t) const { return point(*this) += t; }
point operator - (const point & t) const { return point(*this) -= t; }
point operator * (const type & t) const { return point(*this) *= t; }
point operator / (const type & t) const { return point(*this) /= t; }
point & operator += (const point & t) { return *this = {p::at(0) + t[0], p::at(1) + t[1], p::at(2) + t[2]}; }
point & operator -= (const point & t) { return *this = {p::at(0) - t[0], p::at(1) - t[1], p::at(2) - t[2]}; }
point & operator *= (const type & t) { return *this = {p::at(0) * t, p::at(1) * t, p::at(2) * t}; }
point & operator /= (const type & t) { return *this = {p::at(0) / t, p::at(1) / t, p::at(2) / t}; }
void shake(type eps = 1e-12) { // 微小扰动,去掉四点共面
uniform_real_distribution<type> dist(-0.5, 0.5);
for (auto & t : *this) {
t += dist(rd) * eps;
}
}
struct line : array<point, 2> {
using p = array<point, 2>; // 0 -> 1
point v() { return p::at(1) - p::at(0); }
};
struct face : array<point, 3> {
using p = array<point, 3>; // 从上方看逆时针 0 -> 1 - > 2
point v() { return (p::at(1) - p::at(0)) * (p::at(2) - p::at(0)); }
};
static vector<face> hull(vector<point> q, vector<face> res = {}) {
if (q.size() < 4) return res; // 不允许四点共面
shuffle(q.begin(), q.end(), rd), res.emplace_back(face{q[0], q[1], q[2]}), res.emplace_back(face{q[2], q[1], q[0]});
for (int i = 3; i < q.size(); i++) {
vector<face> nf;
set<pair<point, point>> edge;
for (auto & x : res) {
if (x.v() / (q[i] - x[0]) < 0) nf.emplace_back(x);
else edge.emplace(x[0], x[1]), edge.emplace(x[1], x[2]), edge.emplace(x[2], x[0]);
}
for (auto & [x, y] : edge) {
if (!edge.count({y, x})) nf.emplace_back(face{x, y, q[i]});
}
swap(res, nf);
}
return res;
}
};
void output(__int128 x) {
if(x == 0) {
return;
}
output(x / 10);
cout << (int)(x % 10);
}
void QAQ() {
int n;
cin >> n;
vector<point<int>> 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) {
auto res = point<int>::hull(a);
set<point<int>> s;
for (auto & x : res) {
(ans += x[0] * x[1] / x[2]);
for (auto & idx : x) {
s.emplace(idx);
}
}
vector<point<int>> ta;
for (int i = 0; i < a.size(); i++) {
if (!s.count(a[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(12);
int t = 1;
// cin >> t;
while (t--) {
QAQ();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3652kb
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:
result:
wrong answer 1st lines differ - expected: '1', found: ''