QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#320703#8214. Huge Oil Platformucup-team197#WA 1ms4112kbC++205.0kb2024-02-03 20:17:552024-02-03 20:17:56

Judging History

你现在查看的是最新测评结果

  • [2024-02-03 20:17:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4112kb
  • [2024-02-03 20:17:55]
  • 提交

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){
        push_lazy(i, l, r);
        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]);
    }

    ld 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);
    }

    ld 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 = max((ld)0, st.query(ry_idx + 1, (int)ys.size() - 1));
            }
            else{
                st.update(0, idx, new_p[i].w);
                best_left = max((ld)0, 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";
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4112kb

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: 3832kb

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: 3828kb

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: 3880kb

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'