【vijos1055】奶牛浴场

2015.04.21 19:35 Tue | 2次阅读 | 旧日oi | 固定链接 | 源码

Description

        由于John建造了牛场围栏,激起了奶牛的愤怒,奶牛的产奶量急剧减少。为了讨好奶牛,John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯,每头奶牛都必须在牛场中的一个固定的位置产奶,而奶牛显然不能在浴场中产奶,于是,John希望所建造的浴场不覆盖这些产奶点。这回,他又要求助于Clevow了。你还能帮助Clevow吗?         John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内,并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点,但是产奶点可以位于浴场的轮廓上。         Clevow当然希望浴场的面积尽可能大了,所以你的任务就是帮她计算浴场的最大面积。

Input

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

Output

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

Sample Input

10 10 4 1 1 9 1 1 9 9 9

Sample Output

80

HINT

0< =n< =5000 1< =L,W< =30000

题解

极大化算法,模板,时间复杂度O(S^2),S是障碍点个数。

我的程序

#include <bits/stdc++.h>
using namespace std;
int n,m,k,ans;
struct node
{
    int x,y;
}p[5005];
bool cmp1(const node &a,const node &b)
{
    return a.y<b.y;
}
bool cmp2(const node &a,const node &b)
{
    return a.x<b.x;
}
bool cmp3(const node &a,const node &b)
{
    return a.x>b.x;
}
void work()
{
    for(int i=1;i<=k;i++)
    {
        int y=p[i].y,x=p[i].x,up=n,down=0;
        for(int j=i+1;j<=k;j++)
        {
            ans=max(ans,(p[j].x-x)*(up-down));
            if(p[j].y>y) up=min(up,p[j].y);
            else down=max(down,p[j].y);
        }
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)
    scanf("%d%d",&p[i].x,&p[i].y);
    p[++k].x=0;p[k].y=0;
    p[++k].x=0;p[k].y=n;
    p[++k].x=m;p[k].y=0;
    p[++k].x=m;p[k].y=n;
    sort(p+1,p+k+1,cmp1);
    for(int i=1;i<=k;i++) ans=max(ans,p[i].y*m-p[i-1].y*m);
    sort(p+1,p+k+1,cmp2);
    work();
    sort(p+1,p+k+1,cmp3);
    work();
    cout<<ans<<endl;
}```