QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#320748#8214. Huge Oil Platformucup-team197#WA 1ms4212kbC++206.5kb2024-02-03 20:56:142024-02-03 20:56:15

Judging History

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

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

answer

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <utility>
#include <iomanip>
#include <cmath>
#include <random>
#include <chrono>
#include <set>

using namespace std;
typedef long long ll;
typedef long double ld;

ld ans = 0;

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, l.best_r + r.best_l - 2 * (st_ys[mid + 1] - st_ys[mid]));
            return ret;
        }
    } nd[4 * N];

    void init(){
        for(int i = 0; i < 4 * (st_ys.size()); ++i){
            nd[i] = Node();
        }
    }

    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());
    ld sum_w = 0;
    for(int i = 0; i < ys.size(); ++i){
        st_ys[i] = ys[i] / div;
    }
    for(int i = 0; i < new_p.size(); ++i){
        sum_w += new_p[i].w;
    }
    if(sum_w < ::ans){
        return 0;
    }
    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));
}

clock_t timer = clock();

bool time_left(){
    return (((float)clock() - (float)timer) / (float)CLOCKS_PER_SEC) <= 7.5;
}

set<pair<ll, ll>> s;

ll gcd(ll x, ll y){
    if(!y) return x;
    return gcd(y, x % y);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> p[i].x >> p[i].y >> p[i].w;
        ans = max(ans, (ld)p[i].w);
    }

    mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(p, p + n, mt);

    for(int i = 0; i < n && time_left(); ++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};
            ll g = gcd(abs(diff.x), abs(diff.y));
            diff.x /= g;
            diff.y /= g;
            if(diff.x < 0){
                diff.x = -diff.x;
                diff.y = -diff.y;
            }

            if(s.count(pair{diff.x, diff.y})){
                continue;
            }
            s.insert(pair{diff.x, diff.y});

            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 << ans << " " << i << " " << j << endl;
        }
    }

    if(time_left()){
        for(int i = -10; i <= 10; ++i){
            for(int j = -10; j <= 10; ++j){
                if(!i && !j) continue;

                vector<Point> new_p;
                Point diff{i, j, 0};
                ll g = gcd(abs(diff.x), abs(diff.y));
                diff.x /= g;
                diff.y /= g;
                if(diff.x < 0){
                    diff.x = -diff.x;
                    diff.y = -diff.y;
                }

                if(s.count(pair{diff.x, diff.y})){
                    continue;
                }
                s.insert(pair{diff.x, diff.y});

                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 << ans << " " << i << " " << j << endl;
            }
        }
    }

    cout << fixed << setprecision(12) << ans << "\n";
}
/*
4
1 1 10
1 7 10
4 3 10
2 8 10
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4212kb

input:

2
1 1 1
3 3 1

output:

1170281760988008689.750000000000

result:

wrong answer 1st numbers differ - expected: '1.0000000', found: '1170281760988008704.0000000', error = '1170281760988008704.0000000'