QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#556350#2839. 3D Geometryucup-team1198#AC ✓168ms4040kbC++203.1kb2024-09-10 17:13:352024-09-10 17:13:35

Judging History

This is the latest submission verdict.

  • [2024-09-10 17:13:35]
  • Judged
  • Verdict: AC
  • Time: 168ms
  • Memory: 4040kb
  • [2024-09-10 17:13:35]
  • Submitted

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