QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#566976 | #9316. Boxes | shiqiaqiaya | WA | 0ms | 3920kb | C++17 | 3.4kb | 2024-09-16 04:28:33 | 2024-09-16 04:28:33 |
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 = 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<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> q(n);
for (int i = 0; i < n; i++) {
cin >> q[i][0] >> q[i][1] >> q[i][2];
q[i].shake();
}
auto res = hull(q);
double ans = 0;
for (auto & x : res) {
ans += sqrt(x.norm / x.norm);
}
cout << ans / 2 << "\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: 0
Wrong Answer
time: 0ms
memory: 3920kb
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.000
result:
wrong answer 1st lines differ - expected: '1', found: '0.000'