大佬博客讲解
P1578 奶牛浴场
题目描述
由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于Clevow了。你还能帮助Clevow吗？
John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。
Clevow当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 +7;
typedef long long ll;
struct node {
int x, y;
bool operator < (node& a) const {
if(x == a.x) return y < a.y;
return x < a.x;
}
}p[maxn];
bool cmp(node a, node b) {
if(a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
int main()
{
int L, W, n;
scanf("%d%d%d", &L, &W, &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y);
p[++n].x = 0, p[n].y = 0;
p[++n].x = L, p[n].y = 0;
p[++n].x = 0, p[n].y = W;
p[++n].x = L, p[n].y = W;
sort(p + 1, p + 1 + n);
int ans = 0;
for (int i = 1; i <= n; i++) {//从左向右扫
int h = W, l = 0;
for (int j = i + 1; j <= n; j++) {
ans = max(ans, (p[j].x - p[i].x) * (h - l));
if(p[j].y < p[i].y) l = max(l, p[j].y);
else h = min(h, p[j].y);
}
}
for (int i = n; i >= 1; i--) {//从右向左扫
int h = W, l = 0;
for (int j = i - 1; j >= 1; j--) {
ans = max(ans, (p[i].x - p[j].x) * (h - l));
if(p[j].y < p[i].y) l = max(l, p[j].y);
else h = min(h, p[j].y);
}
}
sort(p + 1, p + 1 + n, cmp);//枚举遗漏的情况
for (int i = 1; i <= n - 1; i++) ans = max(ans, (p[i + 1].y - p[i].y) * L);
printf("%d\n", ans);
return 0;
}