QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363056#8505. Almost Aligneducup-team1191#WA 592ms34584kbC++203.0kb2024-03-23 18:07:512024-03-23 18:07:52

Judging History

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

  • [2024-03-23 18:07:52]
  • 评测
  • 测评结果:WA
  • 用时:592ms
  • 内存:34584kb
  • [2024-03-23 18:07:51]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

const int BIG = 1e9 + 239;

// max
vector<pair<ld, pair<int, int>>> cht(vector<pair<int, int>>& ln) {
    sort(ln.begin(), ln.end());
    vector<pair<ld, pair<int, int>>> ch;
    for (const auto& line : ln) {
        while (!ch.empty()) {
            auto lst = ch.back().second;
            if (lst.first == line.first) {
                break;
            }
            ld x = (ld)(lst.second - line.second) / (line.first - lst.first);
            if (x > ch.back().first) {
                ch.emplace_back(x, line);
                break;
            }
            ch.pop_back();
        }
        if (ch.empty()) {
            ch.emplace_back(make_pair((ld)0.0, line));
            continue;
        }
    }
    //cerr << ch.size() << "\n";
    return ch;
}

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> x(n), y(n);

    int mnx = BIG;
    int mxx = -BIG;
    int mny = BIG;
    int mxy = -BIG;
    for (int i = 0; i < n; i++) {
        cin >> x[i].second >> y[i].second >> x[i].first >> y[i].first;
        mnx = min(mnx, x[i].second);
        mxx = max(mxx, x[i].second);
        mny = min(mny, y[i].second);
        mxy = max(mxy, y[i].second);
    }
    ld ans = ((ll)(mxx - mnx) * (ll)(mxy - mny));

    vector<pair<int, int>> xn(n), yn(n);
    for (int i = 0; i < n; i++) {
        xn[i].first = -x[i].first;
        xn[i].second = -x[i].second;
    }
    for (int i = 0; i < n; i++) {
        yn[i].first = -y[i].first;
        yn[i].second = -y[i].second;
    }

    array<vector<pair<ld, pair<int, int>>>, 4> xs;
    xs[0] = cht(x);
    xs[1] = cht(xn);
    xs[2] = cht(y);
    xs[3] = cht(yn);
    array<int, 4> pos = {0, 0, 0, 0};
    array<ld, 4> ev;
    auto func = [&](ld x) {
        for (int i = 0; i < 4; i++) {
            const auto& line = xs[i][pos[i]].second;
            ev[i] = line.first * x + line.second;
        }
        return (ev[0] + ev[1]) * (ev[2] + ev[3]);
    };
    while (true) {
        bool stop = true;
        for (int i = 0; i < 4; i++) {
            if (pos[i] + 1 < xs[i].size()) {
                stop = false;
                break;
            }
        }
        if (stop) {
            break;
        }

        ld mn;
        int best = -1;
        for (int i = 0; i < 4; i++) {
            if (pos[i] + 1 < xs[i].size()) {
                if (best == -1 || mn > xs[i][pos[i] + 1].first) {
                    best = i;
                    mn = xs[i][pos[i] + 1].first;
                }
            }
        }

        ans = min(ans, func(mn));
        pos[best]++;
    }

    cout << ans << "\n";
}

int main() {
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
0 0 10 10
0 0 10 10
10 10 -10 -10
10 0 -20 0

output:

22.22222222222222222029

result:

ok found '22.222222222', expected '22.222222222', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

3
0 -1 0 2
1 1 1 1
-1 1 -1 1

output:

0.00000000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 4028kb

input:

3
0 -1 0 -2
1 1 1 1
-1 1 -1 1

output:

4.00000000000000000000

result:

ok found '4.000000000', expected '4.000000000', error '0.000000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

1
0 0 0 0

output:

0.00000000000000000000

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

4
1000000 1000000 -1 -1000000
1000000 -1000000 -1000000 1
-1000000 -1000000 1 1000000
-1000000 1000000 1000000 -1

output:

3999984000031.99995183944702148438

result:

ok found '3999984000032.000000000', expected '3999984000032.000000000', error '0.000000000'

Test #6:

score: -100
Wrong Answer
time: 592ms
memory: 34584kb

input:

1000000
-871226 486657 -467526 31395
-65837 846554 469710 -907814
927993 -45099 713462 -276539
261942 483255 746021 811070
63449 -779486 588838 -413687
812070 -87868 -813499 -420768
112521 -622607 -832012 921368
-182120 517379 -401743 -837524
-685985 337832 643014 135144
12895 326935 -495720 930620
...

output:

3999986317541.58295583724975585938

result:

wrong answer 1st numbers differ - expected: '3999996000000.0000000', found: '3999986317541.5830078', error = '0.0000024'