QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#320699 | #8214. Huge Oil Platform | ucup-team197# | WA | 1ms | 3976kb | C++20 | 4.9kb | 2024-02-03 20:12:44 | 2024-02-03 20:12:44 |
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_left = st.query(0, ly_idx - 1);
}
else{
st.update(0, idx, new_p[i].w);
best_right = st.query(ry_idx + 1, (int)ys.size() - 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";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3804kb
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: 3976kb
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: 1ms
memory: 3916kb
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: 3824kb
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:
6009.927312781788
result:
wrong answer 1st numbers differ - expected: '6092.4427126', found: '6009.9273128', error = '0.0135439'