Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const long long inf = 1e18;
- struct Point {
- int x, y;
- Point operator-(const Point& p) const { return {x - p.x, y - p.y}; }
- int64_t operator^(const Point& p) const { return x * 1ll * p.y - y * 1ll * p.x; }
- int64_t dist() const { return x * 1ll * x + y * 1ll * y; }
- bool operator<(const Point& p) const { return x != p.x ? x < p.x : y < p.y; }
- };
- // all point on convex hull are included
- vector<Point> convex_hull(vector<Point> pt) {
- int n = pt.size();
- Point p0 = *std::min_element(pt.begin(), pt.end());
- std::sort(pt.begin(), pt.end(), [&p0](const Point& a, const Point& b) {
- int64_t cp = (a - p0) ^ (b - p0);
- return cp != 0 ? cp > 0 : (a - p0).dist() < (b - p0).dist();
- });
- int i = n - 1;
- for (; i > 0 && ((pt[i] - p0) ^ (pt[i - 1] - p0)) == 0; i--);
- std::reverse(pt.begin() + i, pt.end());
- vector<Point> ch;
- for (auto& p : pt) {
- while (ch.size() > 1) {
- auto& p1 = ch[(int) ch.size() - 1];
- auto& p2 = ch[(int) ch.size() - 2];
- int64_t cp = (p1 - p2) ^ (p - p1);
- if (cp >= 0) break;
- ch.pop_back();
- }
- ch.push_back(p);
- }
- return ch;
- }
- int p[500500];
- int d[500500];
- long long func(Point a, Point b) {
- return (a.x - b.x) * 1ll * (a.y - b.y);
- }
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- int m , n;
- cin >> m >> n;
- for (int i = 0; i < m; i++)
- cin >> p[i] >> d[i];
- vector<Point> ps;
- for (int i = 0; i < n; i++) {
- int q, e;
- cin >> q >> e;
- ps.push_back({e, q});
- }
- ps = convex_hull(ps);
- auto it = max_element(ps.begin(), ps.end(), [](Point a, Point b) {
- return (a.x < b.x || (a.x == b.x && a.y < b.y));
- });
- rotate(ps.begin(), it, ps.end());
- if (ps.size() != 1)
- for (int i = 0; i + 1 < ps.size(); i++) {
- int j = i + 1 == ps.size() ? 0 : i + 1;
- if (!(ps[j].x < ps[i].x && ps[j].y > ps[i].y)) {
- ps.resize(j); // delete with j
- break;
- }
- }
- long long ans = 0;
- for (int i = 0; i < m; i++) {
- int x = d[i];
- int y = p[i];
- Point p {x, y};
- auto it1 = lower_bound(ps.begin(), ps.end(), Point{x, 0}, [](Point a, Point b) {
- return a.x > b.x;
- });
- if (it1 == ps.begin())
- continue;
- it1--;
- auto it2 = lower_bound(ps.begin(), ps.end(), Point{0, y}, [](Point a, Point b) {
- return a.y < b.y;
- });
- int l = it2 - ps.begin();
- int r = it1 - ps.begin();
- if (l > r)
- continue;
- l--;
- while (l + 1 < r) {
- int m1 = (l + r) / 2;
- int m2 = m1 + 1;
- assert(m1 >= 0);
- assert(m2 <= r);
- if (func(ps[m1], p) <= func(ps[m2], p)) {
- l = m1;
- } else {
- r = m1;
- }
- }
- //cout << ps[r].x << " " << ps[r].y << " " << p.x << " " << p.y << " " << func(ps[r], p) << endl;
- //cout << func(ps[r], p) << endl;
- //assert(false);
- ans = max(ans, func(ps[r], p));
- }
- cout << ans;
- return 0;
- }
- /*
- 2 2
- 1 3
- 2 1
- 3 5
- 7 2
- 1 1
- 0 1
- 1000000000 1000000001
- 2 1
- 1000000 1
- 0 1
- 1000000000 1000000001
- 1 1
- 0 2
- 10 2
- 1 2
- 0 1
- 8 2
- 10 2
- 3 3
- 4 3
- 2 5
- 5 0
- 1 3
- 3 2
- 4 1
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement