QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#464463 | #8214. Huge Oil Platform | ucup-team3215 | TL | 1ms | 4012kb | C++23 | 4.4kb | 2024-07-06 09:00:41 | 2024-07-06 09:00:42 |
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 << ")";
}
};
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) {
assert(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);
}
};
Point<ld> lineProj(Point<ll> a, Point<ll> b, Point<ll> p) {
auto v = b - a;
return Point<ld>(p) - Point<ld>(v.perp()) * (v.cross(p - a) / (ld) 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};
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
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[i], a[j], a[k]);
all.emplace_back((z - A).dist() * ((a[j] - a[i]).dot(a[k] - a[i]) < 0 ? -1 : 1), k);
points.emplace_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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3900kb
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: 3940kb
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: 3780kb
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: 0ms
memory: 3796kb
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: 3884kb
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: 3844kb
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: 4012kb
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: -100
Time Limit Exceeded
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...