这道题是我在寒假的模拟赛里碰到的，现在想起来仍觉得余味无穷。题目大意大致如下：给你一个矩形并在其中划出一个最大的子矩形，当然，在这个矩形里有些地方是取不到的，也就是说我们划的这个子矩形不能包含这些点（边界除外）。那么由于时间问题，就让我简单的说一下王知昆论文里的第一种算法（论文链接：http://pan.baidu.com/s/1bnAl6O3）。
首先，我们将所有的点按横坐标从小到大排序一下；然后，我们先设置一个上边界(maxy)和一个下边界(miny)（初始值设为矩形的宽和0），再分别以每一个点为左边界从左到右扫一遍，当扫到一个点时若他的y<maxy 则将当前的上边界就更换为他的y(这样的话无论后面怎么扫，这个点都不会跑到矩形里面)，反之如果y>miny,miny=y;或许你现在可能会有疑问了：如果y>=maxy||y<=miny怎么办，其实这个的话就可以直接不鸟它，理由是如果改变了这是的maxy或miny则前面的点就会有些落到矩形内，这显然是不符合题意的。
当从左往右扫完一遍后，我们可以找出以右边界为边的子矩形(当然，这有可能不是最大的),那么对于以左边界为边的子矩形又该怎么办呢......
想必你已经想到了，不就是再从右往左再扫一遍嘛。好了，这样就完美了吗？是的，如果你提交到vijos就能ac了(数据太弱没办法).但如果再考虑一下就会发现还有分别以左右边界为边的子矩形，这个的话再从上往下扫一遍就行了。
代码如下：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 using namespace std; 5 const int maxn=5000+10; 6 struct node 7 { 8 int x; 9 int y; 10 }p[maxn]; 11 int l,w,n; 12 int maxy,miny; 13 int maxans=0,s=0; 14 bool comp(node a,node b) 15 { 16 return(a.x<b.x); 17 } 18 bool comp1(node a,node b) 19 { 20 return (a.y>b.y); 21 } 22 void qsort(int left,int right) 23 { 24 int i=left,j=right; 25 int mid=p[(left+right)/2].x; 26 while(i<=j) 27 { 28 while(p[i].x<mid) 29 i++; 30 while(p[j].x>mid) 31 j--; 32 if(i<=j) 33 { 34 int temp=p[i].x; 35 p[i].x=p[j].x; 36 p[j].x=temp; 37 i++; 38 j--; 39 } 40 } 41 if(i<right) 42 qsort(i,right); 43 if(j>left) 44 qsort(left,j); 45 } 46 int main() 47 { 48 // freopen("happy.in","r",stdin); 49 // freopen("happy.out","w",stdout); 50 cin>>l>>w; 51 cin>>n; 52 if(n==0) 53 { 54 cout<<l*w<<endl; 55 return 0; 56 } 57 for(int i=1;i<=n;i++) 58 cin>>p[i].x>>p[i].y; 59 sort(p+1,p+n+1,comp); 60 // qsort(1,n); 61 int dx,dy; 62 for(int i=1;i<=n;i++) 63 { 64 miny=0; 65 maxy=w; 66 s=0; 67 for(int j=i+1;j<=n;j++) 68 { 69 dx=p[j].x-p[i].x; 70 dy=maxy-miny; 71 s=dx*dy; 72 maxans=max(s,maxans); 73 // if(p[j].y==p[i].y) 74 // { 75 // break; 76 // } 77 // if(p[j].y>p[i].y&&p[j].y<maxy) 78 // { 79 // maxy=p[j].y; 80 // } 81 // if(p[j].y<p[i].y&&p[i].y>miny) 82 // { 83 // miny=p[j].y; 84 // } 85 if(p[j].y>=p[i].y && p[j].y<maxy) 86 maxy=p[j].y; 87 if(p[j].y<=p[i].y && p[j].y>miny) 88 miny=p[j].y; 89 } 90 dx=l-p[i].x; 91 dy=maxy-miny; 92 s=dx*dy; 93 maxans=max(s,maxans); 94 } 95 for(int i=n;i>=1;i--) 96 { 97 maxy=w; 98 miny=0; 99 s=0; 100 for(int j=i-1;j>=1;j--) 101 { 102 dx=p[i].x-p[j].x; 103 dy=maxy-miny; 104 s=dx*dy; 105 maxans=max(s,maxans); 106 // if(p[i].y==p[j].y) 107 // { 108 // break; 109 // } 110 // if(p[j].y>p[i].y&&p[j].y<maxy) 111 // { 112 // maxy=p[j].y; 113 // } 114 // if(p[j].y<p[i].y&&p[j].y>miny) 115 // { 116 // miny=p[j].y; 117 // } 118 if(p[j].y>=p[i].y && p[j].y<maxy) 119 maxy=p[j].y; 120 if(p[j].y<=p[i].y && p[j].y>miny) 121 miny=p[j].y; 122 } 123 dx=p[i].x; 124 dy=maxy-miny; 125 s=dx*dy; 126 maxans=max(s,maxans); 127 } 128 sort(p+1,p+n+1,comp1); 129 for(int i=1;i<=n;i++) 130 { 131 if(i==1) 132 { 133 dy=w-p[i].y; 134 s=l*dy; 135 maxans=max(maxans,s); 136 } 137 else if(i==n) 138 { 139 dy=p[i].y; 140 s=l*dy; 141 maxans=max(maxans,s); 142 } 143 else 144 { 145 dy=p[i-1].y-p[i].y; 146 s=l*dy; 147 maxans=max(maxans,s); 148 } 149 } 150 cout<<maxans<<endl; 151 return 0; 152 }
