QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#320630 | #8214. Huge Oil Platform | ucup-team197# | TL | 2ms | 4212kb | C++20 | 4.4kb | 2024-02-03 19:13:18 | 2024-02-03 19:13:19 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <utility>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
struct Point{
ll x, y, w;
ll dot(Point p) const {return x * p.x + y * p.y;}
ll cross(Point p) const {return x * p.y - y * p.x;}
};
const int N = 400 + 3;
#define all(x) (x).begin(), (x).end()
int n;
Point p[N];
ll w[N];
vector<ld> st_ys;
struct SegmentTree{
struct Node{
ld sum_w, mx;
ld best_l, best_r;
Node(){
sum_w = mx = best_l = best_r = 0;
}
friend Node merge(const Node &l, const Node &r, int idx_l, int idx_r){
int mid = (idx_l + idx_r) / 2;
Node ret;
ret.sum_w = l.sum_w + r.sum_w;
ret.best_l = max(l.best_l, l.sum_w - 2 * (st_ys[mid + 1] - st_ys[idx_l]) + r.best_l);
ret.best_r = max(r.best_r, r.sum_w - 2 * (st_ys[idx_r] - st_ys[mid]) + l.best_r);
ret.mx = max(l.mx, r.mx);
ret.mx = max({ret.mx, ret.best_l, ret.best_r, l.best_r + r.best_l - 2 * (st_ys[mid + 1] - st_ys[mid])});
return ret;
}
} nd[4 * N];
void init(int i = 0, int l = 0, int r = (int)st_ys.size() - 1){
if(l == r){
nd[i] = Node();
return;
}
int mid = (l + r) >> 1;
init(2 * i + 1, l, mid);
init(2 * i + 2, mid + 1, r);
nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2], l, r);
}
void update(int idx, ll w, int i = 0, int l = 0, int r = (int)st_ys.size() - 1){
if(idx < l || r < idx) return;
if(l == r){
nd[i].sum_w += w;
nd[i].best_l = nd[i].best_r = nd[i].mx = nd[i].sum_w;
return;
}
int mid = (l + r) >> 1;
update(idx, w, 2 * i + 1, l, mid);
update(idx, w, 2 * i + 2, mid + 1, r);
nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2], l, r);
}
ld query(int i = 0, int l = 0, int r = (int)st_ys.size() - 1){
return nd[i].mx;
}
} st;
ld solve2(vector<ll> &ys, vector<Point> &new_p, ll mid_x, ld div){
st_ys.resize(ys.size());
for(int i = 0; i < ys.size(); ++i){
st_ys[i] = ys[i] / div;
}
st.init();
ld ans = 0;
for(int i = 0; i < new_p.size(); ++i){
st.update(lower_bound(all(ys), new_p[i].y) - ys.begin(), new_p[i].w);
if(i == (int)new_p.size() - 1 || new_p[i].x != new_p[i + 1].x){
ld cand = -2 * (new_p[i].x - mid_x) / div;
cand += st.query();
ans = max(ans, cand);
}
}
return ans;
}
ld solve(vector<ll> &xs, vector<ll> &ys, vector<Point> &new_p, ll mid_x, ld div){
sort(all(new_p), [&](auto l, auto r){
return l.x < r.x;
});
vector<Point> left_p, right_p;
for(int i = 0; i < new_p.size(); ++i){
if(new_p[i].x >= mid_x){
right_p.push_back(new_p[i]);
}
}
for(int i = (int)new_p.size() - 1; i >= 0; --i){
if(new_p[i].x <= mid_x){
left_p.push_back(Point{-new_p[i].x, new_p[i].y, new_p[i].w});
}
}
return max(solve2(ys, left_p, -mid_x, div), solve2(ys, right_p, mid_x, div));
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
ld ans = 0;
for(int i = 0; i < n; ++i){
cin >> p[i].x >> p[i].y >> p[i].w;
ans = max(ans, (ld)p[i].w);
}
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
vector<Point> new_p;
Point diff{p[j].x - p[i].x, p[j].y - p[i].y, 0};
for(int k = 0; k < n; ++k){
new_p.push_back(Point{p[k].cross(diff), p[k].dot(diff), p[k].w});
}
ll mid_x = new_p[i].x;
vector<ll> xs, ys;
for(int k = 0; k < n; ++k){
xs.push_back(new_p[k].x);
ys.push_back(new_p[k].y);
}
sort(all(xs));
xs.resize(unique(all(xs)) - xs.begin());
sort(all(ys));
ys.resize(unique(all(ys)) - ys.begin());
ld div = sqrt((ld)diff.x * diff.x + diff.y * diff.y);
ans = max(ans, solve(xs, ys, new_p, mid_x, div));
}
}
cout << fixed << setprecision(12) << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3968kb
input:
2 1 1 1 3 3 1
output:
1.000000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4212kb
input:
3 4 5 5 4 6 7 1 3 8
output:
10.100505063388
result:
ok found '10.1005051', expected '10.1005051', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4136kb
input:
2 0 0 1 1000000 1000000 1000000000
output:
1000000000.000000000000
result:
ok found '1000000000.0000000', expected '1000000000.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3976kb
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.442712623783
result:
ok found '6092.4427126', expected '6092.4427126', error '0.0000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3932kb
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.257312827460
result:
ok found '11878.2573128', expected '11878.2573128', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 4140kb
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.255896932630
result:
ok found '5573.2558969', expected '5573.2558969', error '0.0000000'
Test #7:
score: 0
Accepted
time: 2ms
memory: 4200kb
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.595617883409
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...