QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#576425#8677. Carl’s VacationJWRuixiAC ✓0ms4080kbC++202.9kb2024-09-19 20:18:412024-09-19 20:18:41

Judging History

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

  • [2024-09-19 20:18:41]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:4080kb
  • [2024-09-19 20:18:41]
  • 提交

answer

#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
using namespace std;

using vi = vector<int>;
using db = long double;
constexpr db eps = 1e-12;

struct P {
  db x, y;

#define DEF(o) \
  P& operator o##= (const P &rhs) { x o##= rhs.x, y o##= rhs.y; return *this; } \
  P operator o (const P &rhs) const { return P(*this) o##= rhs; }

  DEF(-) DEF(+)

#undef DEF

#define DEF(o) \
  P& operator o##= (const db &rhs) { x o##= rhs, y o##= rhs; return *this; } \
  P operator o (const db &rhs) const { return P(*this) o##= rhs; }

  DEF(*) DEF(/)

#undef DEF

  db operator * (const P &rhs) const {
    return x * rhs.y - y * rhs.x;
  }

  db norm () {
    return sqrtl(x * x + y * y);
  }

  void chg () {
    swap(x, y);
    x = -x;
  }
} ca[4], cb[4];

IL istream& operator >> (istream &in, P &t) {
  in >> t.x >> t.y;
  return in;
}

struct C {
  P p, q;
  db h;
} a, b;

IL istream& operator >> (istream &in, C &t) {
  in >> t.p >> t.q >> t.h;
  return in;
}

#define D(a, b) (a - b).norm()

IL bool ok (P a, P b, P c, P d) {
  if ((d - b) * (c - d) < 0) {
    return 0;
  }
  return (b - a) * (d - a) >= 0 && (d - a) * (c - a) >= 0;
}

struct V {
  P a, b, c;
  db z;
};

int main () {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> a >> b;
  P aa = a.q - a.p;
  ca[0] = a.p;
  L (i, 1, 3) {
    ca[i] = ca[i - 1] + aa;
    aa.chg();
  }
  P bb = b.q - b.p;
  cb[0] = b.p;
  L (i, 1, 3) {
    cb[i] = cb[i - 1] + bb;
    bb.chg();
  }
  db la = sqrtl((aa.x * aa.x + aa.y * aa.y) * 0.25 + a.h * a.h);
  db lb = sqrtl((bb.x * bb.x + bb.y * bb.y) * 0.25 + b.h * b.h);
  db cfa = la / aa.norm();
  db cfb = lb / bb.norm();
  db as = 0x7ffffffff;
  aa.chg();
  bb.chg();
  L (i, 0, 3) {
    aa.chg();
    P ua = ca[i], va = ca[(i + 1) % 4];
    P A = (ua + va) / 2 + aa * cfa;
    vector<V> v0 = {{A, ua, va, 0}, {ua, ua, va, D(A, ua)}, {va, ua, va, D(A, va)}};
    L (j, 0, 3) {
      bb.chg();
      P ub = cb[j], vb = cb[(j + 1) % 4];
      P B = (ub + vb) / 2 + bb * cfb;
      vector<V> v1 = {{B, ub, vb, 0}, {ub, ub, vb, D(B, ub)}, {vb, ub, vb, D(B, vb)}};
      L (_, 0, 2) {
        auto x = v0[_];
        L (__, 0, 2) {
          auto y = v1[__];
          if (_ == 0 && __ == 0) {
            db a1 = abs((y.a - x.b) * (x.b - x.c)) / (x.b - x.c).norm();
            db a2 = abs((x.a - y.b) * (y.b - y.c)) / (y.b - y.c).norm();
            if (a1 + a2 < la + lb) {
              continue;
            }
          }
          if (ok(x.a, x.b, x.c, y.a) && ok(y.a, y.b, y.c, x.a)) {
            as = min(as, D(x.a, y.a) + x.z + y.z);
          }
        }
      }
    }
  }
  cout << fixed << setprecision(9) << as << '\n';
}
// I love WHQ!

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 4080kb

input:

1 0 0 0 10000
99999 10000 10000 10000 10000

output:

76118.700049220

result:

ok found '76118.7000492', expected '76118.7000492', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

10000 10000 10000 0 10000
0 0 0 10000 10000

output:

32360.679774998

result:

ok found '32360.6797750', expected '32360.6797750', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

0 0 100 100 20
0 0 -5 -5 2

output:

107.365555079

result:

ok found '107.3655551', expected '107.3655551', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

0 0 100 100 20
23 23 18 18 2

output:

88.056757051

result:

ok found '88.0567571', expected '88.0567571', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

0 0 100 100 20
100 100 105 95 2

output:

107.365555079

result:

ok found '107.3655551', expected '107.3655551', error '0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

0 0 100 100 20
44 156 49 151 2

output:

77.704520218

result:

ok found '77.7045202', expected '77.7045202', error '0.0000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

0 0 100 100 20
200 0 205 5 2

output:

224.528035157

result:

ok found '224.5280352', expected '224.5280352', error '0.0000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

0 0 100 100 20
-29 171 -24 176 2

output:

84.368195798

result:

ok found '84.3681958', expected '84.3681958', error '0.0000000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

0 0 100 100 20
-100 100 -105 105 2

output:

107.365555079

result:

ok found '107.3655551', expected '107.3655551', error '0.0000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

0 0 100 100 20
-69 69 -74 74 2

output:

83.294612444

result:

ok found '83.2946124', expected '83.2946124', error '0.0000000'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

0 0 30 0 20
50 20 80 20 20

output:

72.801098893

result:

ok found '72.8010989', expected '72.8010989', error '0.0000000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

0 0 30 0 20
50 20 80 20 140

output:

186.874948276

result:

ok found '186.8749483', expected '186.8749483', error '0.0000000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 4080kb

input:

0 0 30 0 140
50 20 80 20 140

output:

302.264953761

result:

ok found '302.2649538', expected '302.2649538', error '0.0000000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

0 0 30 0 500
50 20 80 20 140

output:

661.328793005

result:

ok found '661.3287930', expected '661.3287930', error '0.0000000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

0 0 30 0 500
50 20 80 20 500

output:

1020.645871961

result:

ok found '1020.6458720', expected '1020.6458720', error '0.0000000'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

0 0 30 0 500
50 20 80 20 2000

output:

2520.361473746

result:

ok found '2520.3614737', expected '2520.3614737', error '0.0000000'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

1137 -1096 229 -599 6253
5792 -405 3433 -9660 2912

output:

16631.267204638

result:

ok found '16631.2672046', expected '16631.2672046', error '0.0000000'

Test #18:

score: 0
Accepted
time: 0ms
memory: 4072kb

input:

-1458 4365 -759 -5184 408
8891 -5111 2941 -8564 6966

output:

14848.097967206

result:

ok found '14848.0979672', expected '14848.0979672', error '0.0000000'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

2289 1693 -2539 850 7414
-4989 3660 8091 2109 6915

output:

18844.470620502

result:

ok found '18844.4706205', expected '18844.4706205', error '0.0000000'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

5431 8457 6717 -6624 2204
-5504 -5607 4032 -674 7792

output:

20847.862166811

result:

ok found '20847.8621668', expected '20847.8621668', error '0.0000000'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3976kb

input:

4274 -9998 -3313 -2647 4590
-792 1334 5701 -8048 3257

output:

16956.483471788

result:

ok found '16956.4834718', expected '16956.4834718', error '0.0000000'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

-1563 -4648 1926 -2970 5843
-1600 9113 -1007 5823 7516

output:

19666.620019250

result:

ok found '19666.6200193', expected '19666.6200193', error '0.0000000'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

-6957 -1204 -2026 2849 1571
9178 1160 -3263 -6525 9297

output:

22798.269165640

result:

ok found '22798.2691656', expected '22798.2691656', error '0.0000000'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

-5254 4877 5836 -1945 4282
8106 -8783 7076 -2291 6168

output:

17820.127104862

result:

ok found '17820.1271049', expected '17820.1271049', error '0.0000000'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

2278 -7979 -200 -9432 528
-8604 1343 -5214 2428 8005

output:

22690.415072392

result:

ok found '22690.4150724', expected '22690.4150724', error '0.0000000'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

5003 277 737 -3626 2886
3492 4353 -446 5788 2426

output:

10058.391619179

result:

ok found '10058.3916192', expected '10058.3916192', error '0.0000000'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

-6582 -2629 -1742 6935 5531
-2010 1455 1794 -3461 9066

output:

20018.375726686

result:

ok found '20018.3757267', expected '20018.3757267', error '0.0000000'

Test #28:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

-8174 -1075 -6736 -2685 6615
-2151 4184 -1716 -308 5064

output:

16260.353232223

result:

ok found '16260.3532322', expected '16260.3532322', error '0.0000000'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

5291 1243 8982 5204 8450
-1177 -5306 -1390 2460 8858

output:

23316.850058254

result:

ok found '23316.8500583', expected '23316.8500583', error '0.0000000'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

-4229 2060 9017 -2659 5812
9887 -9973 5460 -2671 4205

output:

18310.304921594

result:

ok found '18310.3049216', expected '18310.3049216', error '0.0000000'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3972kb

input:

0 0 8 0 3
0 8 8 8 3

output:

10.000000000

result:

ok found '10.0000000', expected '10.0000000', error '0.0000000'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

0 0 8 0 2
8 8 16 8 2

output:

12.000000000

result:

ok found '12.0000000', expected '12.0000000', error '0.0000000'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

0 0 8 0 2
10 10 18 10 2

output:

14.828427125

result:

ok found '14.8284271', expected '14.8284271', error '0.0000000'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

0 0 8 0 100000
10 10 18 10 100000

output:

200002.828747125

result:

ok found '200002.8287471', expected '200002.8287471', error '0.0000000'

Test #35:

score: 0
Accepted
time: 0ms
memory: 3964kb

input:

51412 80788 39091 71527 97605
6327 44899 20415 -12571 86627

output:

194757.486833429

result:

ok found '194757.4868334', expected '194757.4868334', error '0.0000000'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3940kb

input:

-43347 56743 17244 83573 86143
-90081 -3018 -22063 -95528 26489

output:

179973.341845178

result:

ok found '179973.3418452', expected '179973.3418452', error '0.0000000'

Test #37:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

88637 -28248 308 -92620 47395
-57673 62668 -66785 923 49207

output:

210116.821817332

result:

ok found '210116.8218173', expected '210116.8218173', error '0.0000000'

Test #38:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

59768 12643 57116 -71451 64957
-43638 42191 -37837 9851 1875

output:

171578.651505342

result:

ok found '171578.6515053', expected '171578.6515053', error '0.0000000'

Test #39:

score: 0
Accepted
time: 0ms
memory: 4068kb

input:

-46206 -30845 -28470 3652 33497
74620 -92045 75046 -19320 48537

output:

147174.131714615

result:

ok found '147174.1317146', expected '147174.1317146', error '0.0000000'

Test #40:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

65899 65734 27624 70256 81635
-97389 -56422 -91684 -53179 88643

output:

317109.421796759

result:

ok found '317109.4217968', expected '317109.4217968', error '0.0000000'

Test #41:

score: 0
Accepted
time: 0ms
memory: 4076kb

input:

-25117 -50391 569 -34721 73972
-90107 -83510 -46359 -95477 83257

output:

174084.670254182

result:

ok found '174084.6702542', expected '174084.6702542', error '0.0000000'

Test #42:

score: 0
Accepted
time: 0ms
memory: 4072kb

input:

6832 -56636 7968 -59867 82961
6289 -49692 -56413 -38910 90946

output:

184208.611887532

result:

ok found '184208.6118875', expected '184208.6118875', error '0.0000000'

Test #43:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

-100000 -100000 -100000 100000 100000
100000 100000 100000 -100000 100000

output:

482842.712474619

result:

ok found '482842.7124746', expected '482842.7124746', error '0.0000000'

Test #44:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

-79878 -52149 -90171 -65032 95613
-22921 39940 69440 26987 94207

output:

319596.971757630

result:

ok found '319596.9717576', expected '319596.9717576', error '0.0000000'

Extra Test:

score: 0
Extra Test Passed