QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#320700#8214. Huge Oil Platformucup-team197#WA 1ms4052kbC++204.9kb2024-02-03 20:14:252024-02-03 20:14:26

Judging History

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

  • [2024-02-03 20:14:26]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4052kb
  • [2024-02-03 20:14:25]
  • 提交

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'