Untitled
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