QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#567001#9316. BoxesshiqiaqiayaWA 0ms3844kbC++173.6kb2024-09-16 04:59:422024-09-16 04:59:44

Judging History

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

  • [2024-09-16 04:59:44]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3844kb
  • [2024-09-16 04:59:42]
  • 提交

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 = double;
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<point, 3> p;
    point norm;
    face(point a, point b, point c) : p({a, b, c}), norm((b - a) * (c - a)) {}
};

vector<face> hull(vector<point> & q, vector<face> res = {}) {
    res.emplace_back(q[0], q[1], q[2]), res.emplace_back(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) {
            auto & [a, b, c] = x.p;
            if (x.norm / (q[i] - a) > 0) {
                edge.emplace(a, b), edge.emplace(b, c), edge.emplace(c, a);
            } else {
                nf.emplace_back(a, b, c);
            }
        }
        for (auto & [x, y] : edge) {
            if (edge.count({y, x})) continue;
            nf.emplace_back(x, y, q[i]);
        }
        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) {
        shuffle(a.begin(), a.end(), rd);
        auto res = hull(a);
        set<point> s;

        for (auto & x : res) {
            (ans += x.p[0] * x.p[1] / x.p[2]);
            for (auto & idx : x.p) {
                s.emplace(idx);
            }
        }

        vector<point> 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(3);
    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: 0ms
memory: 3844kb

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:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'