QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#556350 | #2839. 3D Geometry | ucup-team1198# | AC ✓ | 168ms | 4040kb | C++20 | 3.1kb | 2024-09-10 17:13:35 | 2024-09-10 17:13:35 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
using ld = long double;
istream& operator>>(istream& in, array<ld, 3>& p) {
for (int i = 0; i < 3; ++i) {
in >> p[i];
}
return in;
}
const ld EPS = 1e-9;
void solve(array<ld, 3> p1, array<ld, 3> p2) {
array<ld, 3> l, r;
cin >> l >> r;
for (int i = 0; i < 3; ++i) {
if (p1[i] > p2[i]) {
p1[i] *= -1;
p2[i] *= -1;
l[i] *= -1;
r[i] *= -1;
}
if (l[i] > r[i]) swap(l[i], r[i]);
l[i] = max(l[i], p1[i]);
r[i] = min(r[i], p2[i]);
if (l[i] >= r[i]) {
cout << "0\n";
return;
}
if (p1[i] < l[i]) {
ld k = (p2[i] - l[i]) / (p2[i] - p1[i]);
for (int j = 0; j < 3; ++j) {
if (j == i) continue;
p2[j] = p1[j] + (p2[j] - p1[j]) * k;
}
p1[i] = l[i];
}
ld d = p1[i];
p1[i] -= d;
p2[i] -= d;
l[i] -= d;
r[i] -= d;
}
/// now p1 = l = 0; p2, r > 0
vector<ld> zs = {l[2], r[2]};
for (int mask = 1; mask <= 3; ++mask) {
ld x = l[0], y = l[1];
if (mask & 1) {
x = r[0];
}
if (mask & 2) {
y = r[1];
}
ld z = p2[2] * (1 - x / p2[0] - y / p2[1]);
if (z > l[2] && z < r[2]) {
zs.push_back(z);
}
}
sort(zs.begin(), zs.end());
auto get_s = [&](ld z) {
ld x1 = r[0], y1 = r[1];
ld x2 = p2[0] * (p2[2] - z) / (p2[2] - p1[2]);
ld y2 = p2[1] * (p2[2] - z) / (p2[2] - p1[2]);
x1 = min(x1, x2);
y1 = min(y1, y2);
if (x1 < EPS || y1 < EPS) return (ld)0;
if (x1 / x2 + y1 / y2 < 1) {
return x1 * y1;
}
ld k1 = (x2 - x1) / x2;
ld k2 = (y2 - y1) / y2;
ld ans = x2 * y2 / 2 * (1 - k1 * k1 - k2 * k2);
return ans;
};
ld ans = 0;
for (int i = 1; i < (int)zs.size(); ++i) {
if (zs[i] - zs[i - 1] < EPS) continue;
array<ld, 3> z = {zs[i - 1], zs[i], (zs[i - 1] + zs[i]) / 2};
array<ld, 3> s;
for (int j = 0; j < 3; ++j) {
s[j] = get_s(z[j]);
}
array<ld, 3> P = {0, 0, 0};
for (int j = 0; j < 3; ++j) {
ld y = s[j];
ld sum = 0, prod = 1;
for (int k = 0; k < 3; ++k) {
if (k == j) continue;
/// cerr << "div: " << z[j] - z[k] << endl;
y /= (z[j] - z[k]);
sum += z[k];
prod *= z[k];
}
P[2] += y;
P[1] -= sum * y;
P[0] += prod * y;
}
ld l = zs[i - 1], r = zs[i];
/// cerr << l << " " << r << " " << P[0] << " " << P[1] << " " << P[2] << endl;
ld res = P[0] * (r - l) + P[1] * (r - l) * (r + l) / 2 + P[2] * (r - l) * (r * r + r * l + l * l) / 3;
ans += res;
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(20);
array<ld, 3> p1, p2;
while (cin >> p1 >> p2) {
solve(p1, p2);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3960kb
input:
0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 2 2 2 0 0 0 1 1 1 0 2 0 2 0 2 1 0 1 0 1 0
output:
0.16666666666666666667 0.83333333333333333332 0.16666666666666666667
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 138ms
memory: 3932kb
input:
-3 -4 2 -5 -5 4 0 0 3 3 4 2 1 5 2 -4 0 0 5 -5 0 -2 -1 3 5 4 2 3 -5 -1 0 -2 -1 -4 -4 -3 -4 4 -2 -2 2 -1 2 2 1 4 0 5 -4 1 0 -5 -2 4 -5 2 -4 5 0 1 2 5 1 -1 0 -3 -1 5 -4 -4 2 -2 2 2 -4 1 3 -1 2 4 2 -2 1 3 2 5 2 -2 -3 -5 -1 0 0 5 4 2 2 5 3 -3 -3 -3 5 4 -4 1 2 -3 2 -4 2 -3 -2 -2 2 -2 -1 -4 -5 3 4 -3 -3 -3...
output:
0 0 0 0 0.70833333333333333332 0 0 15.35565476190476190844 0 6.56250000000000000260 0 0 0 0 0 0 0 0 0 0 0 1.31944444444444444428 0 0.52674897119341563802 4.65000000000000000052 0 0 0 1.92592592592592592494 0 0 0 0 0 15.86888888888888887903 0.09375000000000000000 0 0 0 0 0 0 0 0 0 0 0.259259259259259...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 150ms
memory: 3936kb
input:
-2 -2 -9 1 7 6 -3 -1 -4 -5 -6 2 -3 -4 -9 -10 -5 -4 0 2 -6 7 -9 2 6 4 5 -2 -6 0 8 -8 -3 -3 -10 2 10 -3 -8 -7 -5 -10 -9 -5 1 10 8 -1 7 9 10 6 3 9 -10 -10 -4 0 2 1 -2 4 9 10 5 -4 -6 6 3 7 4 8 6 5 2 3 -7 8 2 3 1 4 -10 7 -7 -3 -6 -10 5 -9 0 3 1 -5 -6 8 5 -3 8 -8 -8 -4 5 -10 4 0 3 1 9 -9 0 -8 8 -3 -7 9 -2...
output:
0 0 0 0 0 16.25573224852071005722 0.16666666666666666667 0 26.20192307692307692561 1.44989106753812636299 0 0 0 0 1.28027681660899653952 0 0 0 13.43124041200964278141 0 0 0 0.04545454545454545454 0 18.29333333333333333655 0 58.04081632653061224164 0 0 1.73611111111111111112 0 0 0 0 144.0000000000000...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 159ms
memory: 3896kb
input:
91 49 27 -66 89 -21 -22 35 78 -64 41 -19 93 87 -92 72 -32 -67 -48 28 -6 -50 20 78 -33 90 41 75 -51 43 89 9 -89 -35 -73 88 13 13 82 82 -40 72 -21 -75 36 15 79 -66 -21 -99 -49 -33 60 78 -27 -86 -64 61 66 96 -77 37 -71 72 -35 -9 38 86 -68 51 65 15 -16 -64 -25 -72 23 81 -20 60 60 -52 -99 19 24 83 27 -11...
output:
0 0 391.12720688094160259585 0 28313.21226415094337980349 0 11477.66256420688603157032 4368.00667700597770659598 14406.48359059555970329569 5814.42720107079119307159 0 50112.71688979635283800462 0 0 0 0 0 0 0 38.15140705509314303367 0 0 0 0 0 72.20194873373299353225 0 0 0 0 0 0 0 1923.68695771616950...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 168ms
memory: 4040kb
input:
-67 241 62 -271 -19 -199 364 487 343 293 433 -343 346 -321 78 -119 68 -487 -319 -45 -165 465 142 491 -310 476 -388 419 409 -124 167 -448 362 233 341 -119 9 -422 290 202 321 -217 310 216 286 172 10 -220 77 107 -282 352 -438 -26 171 81 111 -192 70 -132 376 -361 246 -371 354 -77 -400 -224 457 118 -387 ...
output:
0 417528.64696572187605738691 0 0 49064.27449541284403622399 5211742.51310033129675503005 3370766.24651517351890106511 0 0 84.40513354144987814842 165311.11770842652234136949 0 0 0 52736.15256096316700862303 0 132685.48097236933000431236 0 1436397.51531555298129205767 0 0 0 0 0 7356723.4270074374317...
result:
ok 100000 numbers