QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#320630#8214. Huge Oil Platformucup-team197#TL 2ms4212kbC++204.4kb2024-02-03 19:13:182024-02-03 19:13:19

Judging History

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

  • [2024-02-03 19:13:19]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:4212kb
  • [2024-02-03 19:13:18]
  • 提交

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...

output:


result: