洛谷 P1578 奶牛浴场

题目描述

由于John建造了牛场围栏,激起了奶牛的愤怒,奶牛的产奶量急剧减少。为了讨好奶牛,John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯,每头奶牛都必须在牛场中的一个固定的位置产奶,而奶牛显然不能在浴场中产奶,于是,John希望所建造的浴场不覆盖这些产奶点。这回,他又要求助于Clevow了。你还能帮助Clevow吗?

John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内,并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点,但是产奶点可以位于浴场的轮廓上。

Clevow当然希望浴场的面积尽可能大了,所以你的任务就是帮她计算浴场的最大面积。

输入输出格式

输入格式:

输入文件的第一行包含两个整数L和W,分别表示牛场的长和宽。文件的第二行包含一个整数n,表示产奶点的数量。以下n行每行包含两个整数x和y,表示一个产奶点的坐标。所有产奶点都位于牛场内,即:0<=x<=L,0<=y<=W。

输出格式:

输出文件仅一行,包含一个整数S,表示浴场的最大面积。

输入输出样例

输入样例#1:

10 10
4
1 1
9 1
1 9
9 9

输出样例#1:

80

说明

0<=n<=5000

1<=L,W<=30000

(Winter Camp 2002)

题目分析

初一看,满脸懵逼,不知如何下手,总感觉是道水题,但就是不会写。
这道题是国队大佬王知昆在2003年发表的国家集训队论文《浅谈用极大化思想解决最大子矩阵问题》中提到的2002年冬令营的一道题目。是一个比较经典的模型。
我们定义有效子矩形为内部不包含任何障碍点且边界与坐标轴平行的子矩形。如图所示,第一个是有效子矩形(尽管边界上有障碍点),第二个不是有效子矩形(因为内部含有障碍点)。

首先我们可以对所有的点按照横坐标从小到大的顺序排序,为了方便将右上角也作为一个点加进去,然后以每一个点所在的纵轴作为举矩形的左边界,并确定一个上下界,依次向后枚举每一个点作 为右边界,通过构造的矩形更新答案,以及上下边界。

如图是以点1为左边界来枚举右边界的三个阶段。可见上下边界在一直被不停地更新。

接下来我们会发现一个问题,就是答案其实并没有被完全的更新,我们漏掉了一些情况,通过上边的枚举,我们无法得到一个左边界与整个矩形的左边界完全重合的有效子矩阵以及左右边界都与整个矩阵左右边界分别重合的矩阵,及以下两种情况。

关于第一种情况,我们只需倒着枚举一边,即把所有的点作为右边界,向左枚举,就能找到左边界为矩阵左边界的情况。

对于第二种来说,我们只需要将所有的点按照纵坐标从小到大排序,那么相邻两个点之间的矩形就是如图的矩形。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <cmath>
# define R register
# define LL long long

using namespace std;

int l,w,n,ans;

struct pp{int x,y;}a[5010];

inline void in(R int &a){
R char c = getchar();R int x=0,f=1;
while(!isdigit(c)){if(c == '-') f=-1; c=getchar();}
while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
a = x*f;
}

inline bool cmp(R pp a,R pp b){return a.x<b.x||(a.x == b.x&&a.y<b.y);}
inline bool cmp2(R pp a,R pp b){return a.y<b.y;}

inline void maxx(R int &a,const int b){a>b? 0:a=b;}
inline void minn(R int &a,const int b){a<b? 0:a=b;}

inline int yg(){
in(l),in(w);in(n);
for(R int i=1; i<=n; ++i) in(a[i].x),in(a[i].y);
a[++n] = (pp){l,w};
sort(a+1,a+n+1,cmp);
for(R int i=1; i<=n; ++i)
{
R int up = w,down = 0;
R int j;
for(j=i+1; j<=n; ++j)
{
if(a[j].y<=down||a[j].y>=up||a[j].x == a[i].x) continue;
if((l-a[i].x)*(up-down) <= ans) break;
maxx(ans,(a[j].x-a[i].x)*(up-down));
if(a[j].y==a[i].y) break;
if(a[j].y>a[i].y) minn(up,a[j].y);
else maxx(down,a[j].y);
}
if(j>n) maxx(ans,(l-a[i].x)*(up-down));
}

for(R int i=n; i>=1; --i)
{
R int up = w,down = 0;
R int j;
for(j=i-1; j>=1; --j)
{
if(a[j].y<=down||a[j].y>=up||a[j].x == a[i].x) continue;
if(a[i].x*(up-down) <= ans) break;
maxx(ans,(a[i].x-a[j].x)*(up-down));
if(a[j].y==a[i].y) break;
if(a[j].y>a[i].y) minn(up,a[j].y);
else maxx(down,a[j].y);
}
if(j<1) maxx(ans,a[i].x*(up-down));
}
sort(a+1,a+n+1,cmp2);
for(R int i=1; i<=n; ++i)
maxx(ans,l*(a[i].y-a[i-1].y));
printf("%d",ans);
return 0;
}

int youngsc = yg();
int main(){;}

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. 题目描述
  2. 2. 输入输出格式
    1. 2.1. 输入格式:
    2. 2.2. 输出格式:
  3. 3. 输入输出样例
    1. 3.0.1. 输入样例#1:
    2. 3.0.2. 输出样例#1:
  • 4. 说明
  • 5. 题目分析
  • 6. 代码
  • ,