QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#464471 | #8214. Huge Oil Platform | ucup-team3215 | WA | 7951ms | 4400kb | C++23 | 4.5kb | 2024-07-06 09:21:21 | 2024-07-06 09:21:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
template<class T>
int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
template<typename U>
explicit Point(Point<U> o) : x(o.x), y(o.y) {};
bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
P operator+(P p) const { return P(x + p.x, y + p.y); }
P operator-(P p) const { return P(x - p.x, y - p.y); }
P operator*(T d) const { return P(x * d, y * d); }
P operator/(T d) const { return P(x / d, y / d); }
T dot(P p) const { return x * p.x + y * p.y; }
T cross(P p) const { return x * p.y - y * p.x; }
T cross(P a, P b) const { return (a - *this).cross(b - *this); }
T dist2() const { return x * x + y * y; }
ld dist() const { return sqrtl(dist2()); }
P unit() const { return *this / dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
}
friend ostream &operator<<(ostream &os, P p) {
return os << "(" << p.x << "," << p.y << ")";
}
};
constexpr ld INF = 1e14 + 123;
struct s_tr {
const vector<pair<ld, int>> &all;
vector<array<ld, 4>> s;
s_tr(const vector<pair<ld, int>> &all) : all(all) {
ll n = all.size();
s.resize(4 * n, array<ld, 4>{0, 0, 0, 0});
}
ld len(int pos) {
return all[pos].first - all[pos - 1].first;
}
auto combine(const array<ld, 4> &lhs, const array<ld, 4> &rhs, int m) {
array<ld, 4> res{};
ld l = -2 * len(m);
res[3] = rhs[3] + lhs[3] + l;
res[2] = max(rhs[2], rhs[3] + lhs[2] + l);
res[1] = max(lhs[1], lhs[3] + rhs[1] + l);
res[0] = max({lhs[0], rhs[0], l + rhs[1] + lhs[2]});
return res;
}
void upd(int v, int l, int r, int k, ld val) {
if (l + 1 == r) {
s[v][3] = s[v][2] = s[v][1] = s[v][0] = val;
return;
}
int m = (r + l) / 2;
if (k < m)upd(v * 2 + 1, l, m, k, val);
else upd(v * 2 + 2, m, r, k, val);
s[v] = combine(s[v * 2 + 1], s[v * 2 + 2], m);
}
};
template<typename P>
P lineProj(P a, P b, P p, bool refl = false) {
P v = b - a;
return p - v.perp() * (1 + refl) * v.cross(p - a) / v.dist2();
}
int main() {
cin.tie(0)->sync_with_stdio(false);
mt19937 rng{1000 - 7};
int n = 400;
cin >> n;
vector<Point<ll>> a(n);
vector<ll> w(n);
for (int i = 0; i < n; ++i) {
a[i].x = rng() % (int) 1e6;
a[i].y = rng() % (int) 1e6;
w[i] = rng() % (int) 1e9;
cin >> a[i].x >> a[i].y >> w[i];
}
ld res{0};
vector<pair<int, int>> rofl;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j)rofl.emplace_back(i, j);
}
shuffle(rofl.begin(), rofl.end(), rng);
while ((ld) clock() / CLOCKS_PER_SEC < 7.95 && rofl.size()) {
auto [i, j] = rofl.back();
rofl.pop_back();
Point<ld> A(a[i]);
Point<ld> B(a[j]);
auto solve = [&](bool inv) {
vector<pair<ld, ll>> points;
vector<pair<ld, int>> all;
for (int k = 0; k < n; ++k) {
Point<ld> C(a[k]);
if ((inv ? -1 : 1) * (a[j] - a[i]).cross(a[k] - a[i]) >= 0) {
auto z = lineProj(A, B, C);
all.emplace_back((z - A).dist() * ((a[j] - a[i]).dot(a[k] - a[i]) < 0 ? -1 : 1), k);
points.push_back({(z - C).dist(), k});
}
}
sort(all.begin(), all.end());
vector<int> pos(n);
for (int j = 0; j < all.size(); ++j) {
pos[all[j].second] = j;
}
sort(points.begin(), points.end());
int N = all.size();
s_tr tree(all);
for (auto [d, k]: points) {
int p = pos[k];
tree.upd(0, 0, N, p, w[k]);
res = max(res, -2 * d + tree.s[0][0]);
}
};
solve(false);
solve(true);
}
cout << fixed << setprecision(20);
cout << res;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3896kb
input:
2 1 1 1 3 3 1
output:
1.00000000000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4124kb
input:
3 4 5 5 4 6 7 1 3 8
output:
10.10050506338833465822
result:
ok found '10.1005051', expected '10.1005051', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
2 0 0 1 1000000 1000000 1000000000
output:
1000000000.00000000000000000000
result:
ok found '1000000000.0000000', expected '1000000000.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3924kb
input:
20 328 207 21 365 145 188 347 79 41 374 335 699 288 250 97 32 267 131 296 332 434 2 91 36 139 43 21 26 455 696 57 135 410 14 500 396 255 181 646 103 114 593 309 351 787 207 316 138 440 416 806 413 349 695 413 201 501 455 396 442
output:
6092.44271262378278919414
result:
ok found '6092.4427126', expected '6092.4427126', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3908kb
input:
20 38 207 766 202 485 964 257 466 900 205 486 738 166 53 716 61 94 881 252 165 182 63 292 612 225 278 242 224 242 566 381 196 702 56 494 997 268 288 884 379 227 3 357 271 975 55 73 678 260 55 623 399 369 515 116 354 580 404 239 950
output:
11878.25731282745992789529
result:
ok found '11878.2573128', expected '11878.2573128', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3908kb
input:
20 249 215 320 38 48 229 457 366 56 36 142 186 44 96 935 97 190 143 215 218 123 116 486 291 304 232 463 429 297 29 479 475 97 97 198 405 69 395 121 381 121 926 137 197 972 410 91 218 87 421 737 117 390 144 319 287 170 353 302 754
output:
5573.25589693263021695557
result:
ok found '5573.2558969', expected '5573.2558969', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4068kb
input:
20 474 215 66 376 120 6 367 259 211 362 293 34 416 407 554 133 292 894 171 278 871 459 187 674 383 192 980 352 78 899 83 27 684 138 185 709 357 234 359 390 241 40 418 124 161 258 348 462 408 59 851 110 184 668 28 447 761 20 131 367
output:
8510.59561788340911370199
result:
ok found '8510.5956179', expected '8510.5956179', error '0.0000000'
Test #8:
score: 0
Accepted
time: 7947ms
memory: 4248kb
input:
400 979422 264252 76260 922920 334464 58710 87057 798078 39652 602478 649867 49073 388746 161788 44501 727471 373113 28061 944959 505744 22145 191465 164645 49421 102241 771049 65953 44911 762286 34082 112779 537040 98117 688054 585935 53647 391845 931395 55355 788464 698271 91449 984533 409449 8331...
output:
35610300.74428987376086297445
result:
ok found '35610300.7442899', expected '35610300.7442899', error '0.0000000'
Test #9:
score: 0
Accepted
time: 7935ms
memory: 4156kb
input:
400 972392 809281 95619 19054 872671 65516 732236 376176 38922 412232 147107 36902 242843 486112 34287 311141 416172 5612 453695 775962 79060 806457 678364 29585 324358 953486 58858 532543 378842 67089 20301 449627 86941 252735 242252 66239 335667 454693 40007 563783 444579 49920 663605 128448 3095 ...
output:
35334006.33097682120933313854
result:
ok found '35334006.3309768', expected '35334006.3309768', error '0.0000000'
Test #10:
score: 0
Accepted
time: 7943ms
memory: 4248kb
input:
400 718289 727141 23905 849810 500522 44241 890554 385825 70996 597411 423432 99133 994251 463004 32770 388843 280170 47562 664865 319482 48403 353770 474376 52218 508270 890719 28901 80661 697191 77469 459811 411012 23750 741501 408373 60551 163462 269625 56148 406785 260156 41900 337932 855364 578...
output:
36725958.76718687036554911174
result:
ok found '36725958.7671869', expected '36725958.7671869', error '0.0000000'
Test #11:
score: 0
Accepted
time: 7951ms
memory: 4092kb
input:
400 6840 184362 43862 608935 154893 10000000 746897 683314 71237 255918 899062 94342 478185 102216 1923 890855 323689 44654 467417 577805 20 919997 267591 21891 303668 171438 29365 324647 818449 18945 229942 874921 22870 174645 613823 31193 559386 859851 36262 156698 936021 86194 968031 522125 75799...
output:
36590958.86049337056829244830
result:
ok found '36590958.8604934', expected '36590958.8604934', error '0.0000000'
Test #12:
score: 0
Accepted
time: 7940ms
memory: 4400kb
input:
400 213928 419916 45837 334919 278535 7824 100882 416988 26147 682280 524709 85794 569137 589867 48913 344075 156956 4813 87794 655931 25690 285467 798402 55113 295984 894760 44628 535011 461670 72400 917862 461662 90830 544780 751382 81071 588022 966874 10000000 872058 880760 39315 216881 626161 22...
output:
46173511.87199231090926332399
result:
ok found '46173511.8719923', expected '46173511.8719923', error '0.0000000'
Test #13:
score: 0
Accepted
time: 7947ms
memory: 4180kb
input:
400 937407 829281 77362 837708 843713 34574 77624 684540 68232 786430 452449 38426 486327 341660 86859 964636 122535 12764 699975 284575 84208 806142 721010 10955 464680 787842 37887 395874 727033 70790 59849 84503 90263 557124 876914 45080 168385 390089 16463 6894 13302 8291 380410 621577 47431 992...
output:
45704049.96153425236843759194
result:
ok found '45704049.9615343', expected '45704049.9615343', error '0.0000000'
Test #14:
score: 0
Accepted
time: 7944ms
memory: 4160kb
input:
400 769436 473525 91179 925212 211008 73863 393798 496395 71452 241696 745916 92387 519975 24414 32489 867615 821099 81949 644522 605802 2383 237926 379309 38924 389221 50127 90627 201042 315597 28025 314735 422671 18588 616409 476289 21284 397182 521279 80524 190834 918992 35979 405770 829871 41232...
output:
46077961.21213435679965186864
result:
ok found '46077961.2121344', expected '46077961.2121344', error '0.0000000'
Test #15:
score: -100
Wrong Answer
time: 7940ms
memory: 4208kb
input:
400 661885 939867 75528 487494 846559 71593 290098 369543 36755 931898 794760 63921 480058 761470 19842 426135 379317 3551 627245 832185 26033 598705 59485 2540 941138 844706 6210 377586 312034 96388 398374 295001 41568 874081 558382 41501 933464 285407 30933 444410 590787 18450 950252 399446 44906 ...
output:
45281605.93640943580612656660
result:
wrong answer 1st numbers differ - expected: '45282826.9191970', found: '45281605.9364094', error = '0.0000270'