题目链接
https://vjudge.net/problem/UVALive-3695
题意
给定平面上的n(1<=n<=100)个点，找一个矩形，使得边界上包含尽可能多的点
分析
先考虑朴素的解法：枚举四条边，再统计边界上的点数。时间复杂度O（n^5).
然后考虑优化：部分枚举，只枚举上下边界和右边界；而左边界在枚举右边界的同时进行维护。这样部分枚举的时间复杂度已经到了O(n^3)。如果继续使用朴素算法去统计点数，不仅左边界不好维护，总时间复杂度也会到达O(n^4).导致时间超限。
优化统计点数的算法：先从低维出发看看能否得到一些启发，统计一维上[l,r]点的数目的话，常用sum[i]来存放[0,i]的点的数目，这样sum[r]-sum[l-1]即为所求。
延伸到二维的情况，我们可以用left[i]来存放右边界x=i的左侧（不包括x=i）的区域中上下两条边界上的点数，这样对于从x=i到x=j的矩形的上下边界上的点数为left[j]-left[i]+on[i]+on2[j].其中on[i]表示左边界上的点数（不含在上下边界上的），on2[j]表示右边上的点数（含在上下边界上的）。
现在，问题的当务之急是如何求left，on，on2.
同理用降维的思想(sum[i]=sum[i-1]+A[i])考虑求left可以得到一个启发，left[i]=left[i-1]+on2[i]-on[i].
而on和on2可以在枚举上下边界后用O(n)时间统计出来，也就是O(n^3)的时间复杂度，可以接受。
到这里，就只剩下一个问题了，如何在枚举右边界的同时维护左边界？
因为ans=left[j]+on2[j]+on[i]-left[i],所以对确定的j，要找一个i使得on[i]-left[i]最大。故维护左边界只要维护好on[i]-left[i]即可，令now=on[1]-left[1],随着j从2枚举到k，now=max(now,on[j]-left[j]).
代码
#include <cstdio>
#include <cstring>
#include <algorithm> //为了使用unique()函数去重using namespace std;const int maxn=110;
struct point
{int x,y;bool operator<(const point &o)const{return x<o.x;}
} p[maxn];
int y[maxn],N,left[maxn],on[maxn],on2[maxn];int solve()
{//排序、去重sort(p,p+N);sort(y,y+N);memset(left,0,sizeof(left));int m=unique(y,y+N)-y;if(m<=2)return N;int ans=0,now;for(int a=0; a<m; a++) //枚举上界for(int b=a+1; b<m; b++) //枚举下界{int ymin=y[a],ymax=y[b],k=0;for(int i=0; i<N; i++){if(i==0 || p[i].x!=p[i-1].x){k++; //不同的列on[k]=0;on2[k]=0;left[0]=0;}left[k]=k==1?0:left[k-1]+on2[k-1]-on[k-1];if(p[i].y<ymax && p[i].y>ymin){on[k]++;}if(p[i].y<=ymax && p[i].y>=ymin)on2[k]++;}if(k<=2)return N;now=on[1]-left[1];for(int j=2; j<=k; j++){ans=max(ans,left[j]+on2[j]+now);now=max(now,on[j]-left[j]);}}return ans;
}int main()
{int kase=1;while(~scanf("%d",&N) && N){//输入for(int i=0; i<N; i++){scanf("%d%d",&p[i].x,&p[i].y);y[i]=p[i].y;}printf("Case %d: %d\n",kase++,solve());}return 0;
}