Untitled

mail@pastecode.io avatar
unknown
plain_text
14 days ago
4.0 kB
1
Indexable
Never
#include<bits/stdc++.h>

#define ll long long
#define pp push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ld long double
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define ones(x) __builtin_popcountll(x)
//#define int ll

using namespace std;

void Drakon() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef Clion
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}

unsigned long long inf = 1e10;
const double EPS = 1e-6;
const int MOD = 1000000007, N = 200005, LOG = 25;

ll mul(const ll &a, const ll &b) {
    return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
}

ll add(const ll &a, const ll &b) {
    return (a + b + 2 * MOD) % MOD;
}

ll pw(ll x, ll y) {
    ll ret = 1;
    while (y > 0) {
        if (y % 2 == 0) {
            x = mul(x, x);
            y = y / 2;
        } else {
            ret = mul(ret, x);
            y = y - 1;
        }
    }
    return ret;
}

ll stress(vector<pair<int, int>> &vec1, vector<pair<int, int>> &vec2) {
    ll ret = 0;
    for (int i = 0; i < vec1.size(); ++i) {
        for (int j = 0; j < vec2.size(); ++j) {
            if(vec2[j].second <= vec1[i].second)continue;
            ret = max(ret, 1ll * (vec2[j].second - vec1[i].second) * (vec2[j].first - vec1[i].first));
        }
    }
    return ret;
}

bool cmp(pair<int, int> &a, pair<int, int> &b) {
    return a.second > b.second;
}

ll calc(vector<pair<int, int>> &vec1, vector<pair<int, int>> &vec2) {
    ll ret = 0;
    sort(all(vec1), cmp);
    sort(all(vec2), cmp);
    int l = 0;
    vector<pair<int, int>> poly;
    for (int i = 0; i < vec1.size(); ++i) {
        while (l < vec2.size() && vec2[l].second >= vec1[i].second) {
            if(!poly.empty() && vec2[l].second == poly.back().second && vec2[l].first > poly.back().first)poly.pop_back();
            if(poly.empty() || vec2[l].first > poly.back().first) {
                poly.push_back(vec2[l]);
            }
            l ++;
        }

        int st = 0, en = (int)poly.size() - 1;
        while (st <= en) {
            int m1 = st + (en - st) / 3;
            int m2 = en - (en - st) / 3;
            ll val1 = (poly[m1].second - vec1[i].second) * (poly[m1].first - vec1[i].first);
            ll val2 = (poly[m2].second - vec1[i].second) * (poly[m2].first - vec1[i].first);
            ret = max(ret, val1);
            ret = max(ret, val2);
            if(val1 > val2) {
                en = m2 - 1;
            }
            else {
                st = m1 + 1;
            }
        }
    }

    return ret;
}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
//    vector<pair<int, int>> vec1 = {{6, 18}, {11, 9}, {8, 3}};
//    vector<pair<int, int>> vec2 = {{12, 20}, {5, 6}, {6, 2}};
//    calc(vec1, vec2);

    for (int i = 0; i < 100; ++i) {
        int n = 6, m = 6;
        vector<pair<int, int>> vec1(n);
        for (int j = 0; j < n; ++j) {
            vec1[j].first = rnd() % 20 + 1;
            vec1[j].second = rnd() % 20 + 1;
        }

        vector<pair<int, int>> vec2(m);
        for (int j = 0; j < m; ++j) {
            vec2[j].first = rnd() % 20 + 1;
            vec2[j].second = rnd() % 20 + 1;
        }

        ll val1 = stress(vec1, vec2), val2 = calc(vec1, vec2);
        if(val1 != val2) {
            cout << val1 << " " << val2 << endl;
            for (int j = 0; j < n; ++j) {
                cout << vec1[j].first << ' ' << vec1[j].second << endl;
            }
            cout << endl;
            for (int j = 0; j < m; ++j) {
                cout << vec2[j].first << ' ' << vec2[j].second << endl;
            }
            return;
        }
    }
}

signed main() {
    Drakon();
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}
Leave a Comment