QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#320700 | #8214. Huge Oil Platform | ucup-team197# | WA | 1ms | 4052kb | C++20 | 4.9kb | 2024-02-03 20:14:25 | 2024-02-03 20:14:26 |
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];
int cnt_ys;
struct SegmentTree{
ld mx[4 * N];
ld lp[4 * N];
void init(){
for(int i = 0; i < 4 * cnt_ys; ++i){
mx[i] = lp[i] = 0;
}
}
void push_lazy(int i, int l, int r){
if(!lp[i]) return;
mx[i] += lp[i];
if(l != r){
lp[2 * i + 1] += lp[i];
lp[2 * i + 2] += lp[i];
}
lp[i] = 0;
}
void update(int sl, int sr, ld w, int i = 0, int l = 0, int r = cnt_ys - 1){
if(sr < l || r < sl) return;
if(sl <= l && r <= sr){
lp[i] += w;
push_lazy(i, l, r);
return;
}
int mid = (l + r) >> 1;
update(sl, sr, w, 2 * i + 1, l, mid);
update(sl, sr, w, 2 * i + 2, mid + 1, r);
mx[i] = max(mx[2 * i + 1], mx[2 * i + 2]);
}
ll squery(int sl, int sr, int i = 0, int l = 0, int r = cnt_ys - 1){
push_lazy(i, l, r);
if(sr < l || r < sl) return 0;
if(sl <= l && r <= sr) return mx[i];
int mid = (l + r) >> 1;
ll l_ans = squery(sl, sr, 2 * i + 1, l, mid);
ll r_ans = squery(sl, sr, 2 * i + 2, mid + 1, r);
return max(l_ans, r_ans);
}
ll query(int sl, int sr){
if(sl > sr) return 0;
return squery(sl, sr);
}
} st;
ld solve2(vector<ll> &ys, vector<Point> &new_p, ll mid_x, ld div, Point p1, Point p2){
cnt_ys = ys.size();
ld ans = 0;
ld best_left = 0, best_right = 0;
ll ly = min(p1.y, p2.y), ry = max(p1.y, p2.y);
ld sum = -2 * (ry - ly) / div;
int ly_idx = lower_bound(all(ys), ly) - ys.begin();
int ry_idx = lower_bound(all(ys), ry) - ys.begin();
st.init();
for(int i = ry_idx + 1; i < ys.size(); ++i){
st.update(i, i, -2 * (ys[i] - ys[ry_idx]) / div);
}
for(int i = 0; i < ly_idx; ++i){
st.update(i, i, -2 * (ys[ly_idx] - ys[i]) / div);
}
for(int i = 0; i < new_p.size(); ++i){
int idx = lower_bound(all(ys), new_p[i].y) - ys.begin();
if(ly_idx <= idx && idx <= ry_idx){
sum += new_p[i].w;
}
else{
if(idx > ry_idx){
st.update(idx, (int)ys.size() - 1, new_p[i].w);
best_right = st.query(ry_idx + 1, (int)ys.size() - 1);
}
else{
st.update(0, idx, new_p[i].w);
best_left = st.query(0, ly_idx - 1);
}
}
ld cand = -2 * (new_p[i].x - mid_x) / div;
cand += best_left + best_right + sum;
ans = max(ans, cand);
}
return ans;
}
ld solve(vector<ll> &xs, vector<ll> &ys, vector<Point> &new_p, ll mid_x, ld div, Point p1, Point p2){
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});
}
}
ld ans = solve2(ys, right_p, mid_x, div, p1, p2);
p1.x = -p1.x;
p2.x = -p2.x;
ans = max(ans, solve2(ys, left_p, -mid_x, div, p1, p2));
return ans;
}
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, new_p[i], new_p[j]));
}
}
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: 3880kb
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: 4052kb
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: 3888kb
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: -100
Wrong Answer
time: 1ms
memory: 3988kb
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:
6091.614290194693
result:
wrong answer 1st numbers differ - expected: '6092.4427126', found: '6091.6142902', error = '0.0001360'