P1578. 奶牛浴场

发表于 2024-01-10 分类于洛谷阅读次数： Waline：本文字数： 368 阅读时长 ≈ 1 分钟

考点

最大子矩形
障碍物法

题解

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 50;
int n, ans, L, W;

struct node {
  int x_, y_;
} a[maxn];

bool cmpx(node &x, node &y) { return x.x_ < y.x_; }

bool cmpy(node &x, node &y) { return x.y_ < y.y_; }

int main() {
  cin >> L >> W >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i].x_ >> a[i].y_;
  // 四个顶点也算障碍点
  a[++n] = {0, 0}, a[++n] = {0, W}, a[++n] = {L, 0}, a[++n] = {L, W};
  // 从左到右扫一遍
  sort(a + 1, a + 1 + n, cmpx);
  for (int i = 1; i < n; ++i) {
    int u = 0, d = W;
    for (int j = i + 1; j <= n; ++j) {
      int l = a[i].x_, r = a[j].x_;
      ans = max(ans, (r - l) * (d - u));
      a[i].y_ <= a[j].y_ ? d = min(d, a[j].y_) : u = max(u, a[j].y_);
    }
  }
  // 从上到下扫一遍
  sort(a + 1, a + 1 + n, cmpy);
  for (int i = 1; i < n; ++i) {
    int u = 0, d = L;
    for (int j = i + 1; j <= n; ++j) {
      int l = a[i].y_, r = a[j].y_;
      ans = max(ans, (r - l) * (d - u));
      a[i].x_ <= a[j].x_ ? d = min(d, a[j].x_) : u = max(u, a[j].x_);
    }
  }
  cout << ans;
  return 0;
}