「vijos1055」奶牛浴场
描述
由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于Clevow了。你还能帮助Clevow吗？
John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。
Clevow当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。
输入格式
输入文件的第一行包含两个整数L和W，分别表示牛场的长和宽。文件的第二行包含一个整数n，表示产奶点的数量。以下n行每行包含两个整数x和y，表示一个产奶点的坐标。所有产奶点都位于牛场内，即：0<=x<=L，0<=y<=W。
输出格式
输出文件仅一行，包含一个整数S，表示浴场的最大面积。
代码
本题可参看论文浅谈用极大化思想解决最大子矩形问题
|
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 |
#include<iostream> #include<algorithm> #include<cstdio> using namespace std; struct data{ int x,y; }p[5001]; inline bool cp1(data a,data b){return a.x<b.x;} inline bool cp2(data a,data b){return a.y<b.y;} inline bool cp3(data a,data b){return a.y>b.y;} int main() { int l,w,ans=0; scanf("%d%d",&l,&w); int n;scanf("%d",&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=w;p[n].y=0; p[++n].x=w;p[n].y=l; p[++n].x=0;p[n].y=l; sort(p+1,p+n+1,cp1); for(int i=2;i<=n;i++) ans=max(ans,(p[i].x-p[i-1].x)*l); sort(p+1,p+n+1,cp2); for(int i=1;i<=n;i++) { int u=0,d=w; for(int j=i+1;j<=n;j++) { if(p[j].x<=d&&p[j].x>=u) { ans=max(ans,(d-u)*(p[j].y-p[i].y)); if(p[j].x>p[i].x)d=p[j].x; else u=p[j].x; } if(u==d)break; } } sort(p+1,p+n+1,cp3); for(int i=1;i<=n;i++) { int u=0,d=w; for(int j=i+1;j<=n;j++) { if(p[j].x<=d&&p[j].x>=u) { ans=max(ans,(d-u)*(p[i].y-p[j].y)); if(p[j].x>p[i].x)d=p[j].x; else u=p[j].x; } if(u==d)break; } } printf("%d",ans); return 0; } |
之前的代码有误，予以修改
计数器 9854416
OI 课件=>
OI 课件=>
QAQ..hack：
4 7
5
0 6
0 0
3 2
1 0
0 3
正解21，输出28