# 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;
}

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();
}
}```