奶牛浴场
happy.exe
【问题描述】
由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于Clevow了。你还能帮助Clevow吗？
John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。
Clevow当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。
【输入文件】
输入文件的第一行包含两个整数L和W，分别表示牛场的长和宽。文件的第二行包含一个整数n，表示产奶点的数量。以下n行每行包含两个整数x和y，表示一个产奶点的坐标。所有产奶点都位于牛场内，即：0<x<L，0<y<W。
【输出文件】
输出文件仅一行，包含一个整数S，表示浴场的最大面积。
【输入输出样例】
happy.in
|
happy.out
|
10 10
4
1 1
9 1
1 9
9 9
|
80
|
【参数约定】
0<n<5000
1<L,W<30000
【解析】
不难看出，为了取得最大面积，矩形的四条边必须经过产奶点或边界。
于是考虑贪心，假设产奶点A、B（$y_A<y_B$）分别位于最终取得的矩形的左侧和右侧，点C满足(1)$x_A<x_C<x_B$，(2)$\forall P$满足$x_A<x_P<x_B$且$y_P<y_A,\;$有$y_P\leqslant y_C$。通俗地说，点C是直线$x=x_A$和直线$x=x_B$之间位于点A下方的最高的点。类似地，点D满足(1)$x_A<x_D<x_B$，(2)$\forall P$满足$x_A<x_P<x_B$且$y_P<y_A,\;$有$y_P\leqslant y_C$。我们便得到了一个以A、B为左右边界的矩形。如图：
这样，只要枚举所有的A、B即可得到答案。至于C、D，可以用平衡树确定。
具体是实现方式是：将所有的产奶点按x坐标排升序，枚举A，在A的右侧枚举B，将B的y坐标加入map <int,int> S中，使用map::lower_bound()和map::upper_bound()确定C、D，当然假如C或D不存在，矩形的下界或上界就是区域的边界，更新答案。
这种做法虽然是正确的，但复杂度与实现难度都较大，而且不便于判断与边界重合的情况。
我进一步简化枚举过程：引入辅助变量up和low，分别表示$y_D$和$y_C$，枚举A，在A的右侧枚举B，用B的y坐标更新up和low，更新答案。实现如下：
for (int i = 0; i<n; i++)
{
int up = W, low
= 0;
int j = i;
while (point[j].x
== point[i].x)j++;
int lastsame =
j;
for (; j<n;
j++)
{
if (point[j].x
!= point[lastsame].x)
{
for (int k =
lastsame; k<j; k++)
{
if (point[k].y
>= point[i].y)up = min(up,
point[k].y);
else low = max(low, point[k].y);
}
lastsame = j;
}
ans = max(ans, (point[j].x - point[i].x)*(up
- low));
}
ans = max(ans, (L - point[i].x)*(up - low));
}
现在只剩下区域的左侧位于边界上的特殊情况了，这种情况不好直接处理，一个比较容易的方法就是竖着再枚举一遍。
但这样处理还会遗漏一种更加特殊的情况：矩形的四条边都位于边界上，对于这种情况，n一定为0，直接特判即可。
【参考程序】
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
void read(int &x)
{
x =
0; char ch = getchar(); bool f =
0;
while (ch>'9' ||
ch<'0') {if(ch=='-')f=1;ch=getchar();}
while (ch >= '0'&&ch
<= '9') {x = x * 10 + ch - 48; ch = getchar();}
if (f)x = -x;
}
struct point_t
{
bool operator<(const point_t &b)const
{
if (x != b.x)return x<b.x;
return y<b.y;
}
int x,
y;
}point[5000];
int main()
{
freopen("happy.in", "r", stdin);
freopen("happy.out", "w", stdout);
int n,
L, W;
read(L);
read(W);
read(n);
if (n
== 0)
{
cout << L*W << endl;
return 0;
}
for (int i = 0; i<n; i++)
{
read(point[i].x);
read(point[i].y);
}
sort(point,
point + n);
int ans
= 0;
for (int i = 0; i<n; i++)
{
int up = W, low = 0;
int j = i;
while (point[j].x == point[i].x)j++;
int lastsame = j;
for (; j<n; j++)
{
//这么做是为了防止有多个点的x坐标相同
if (point[j].x != point[lastsame].x)
{
for (int k = lastsame; k<j; k++)
{
if(point[k].y>=point[i].y)up = min(up, point[k].y);
else low = max(low, point[k].y);
}
lastsame = j;
}
ans = max(ans, (point[j].x - point[i].x)*(up - low));
}
if (L != point[lastsame].x)
{
for (int k = lastsame; k<n; k++)
{
if (point[k].y >= point[i].y)up = min(up, point[k].y);
else low = max(low, point[k].y);
}
}
ans = max(ans, (L - point[i].x)*(up - low));
}
/*
还剩下的竖着枚举的情况交给读者自己实现。
如果不写，也可以通过官方数据。
但不保证在OJ上提交可以通过。
*/
cout << ans << endl;
return 0;
}
没有评论:
发表评论