题目连接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=91208#problem/G
题意： 给出平面上的n个点，找出一个矩形，使得边界上含有尽量多的点；输出最多的点数。
分析：
先枚举上下边界，然后从左到右扫，扫描一遍所有的点，计算l， on， on2数组，枚举右边界，维护on[i] - L[i]的最大值。
其中对于第i列，l[i]表示竖线左边位于上下边界的点数（不包括位于竖线i）, on[i]表示竖线上位于上下边界之间的点数（和on2[i]的区别就是on[i]不统计位于上下边界的点数），
所以当给定左右边界i和j的话，矩形边界上的点数为l[j]+on2[j]+on[i]-l[i],当右边界j确定的时候，on[i]-left[i]要最大的；
特别的就是当n个点的横坐标或纵坐标小于等于2种时，那么这种情况ans = n。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
int max(int a,int b)
{
if(a>b) return a;
else return b;
}
struct Point {
int x, y;
bool operator< (const Point& cmp) const{
return x < cmp.x;
}
}p[maxn];
int n,m,y[maxn],on[maxn],on2[maxn],l[maxn];
int sove()
{
sort(p, p+n);
sort(y, y+n);
m = unique(y, y+n)-y; //统计具有不同y坐标的点的个数
if(m <= ) return n;
int ans = ;
for(int a=;a<m;a++)
{
for(int b=a+;b<m;b++)
{
int k=;
for(int i=;i<n;i++)
{
if(i==||p[i].x!=p[i-].x)
{
k++;
on2[k]=on[k]=;
l[k]=l[k-]+on2[k-]-on[k-];
}
if(y[a]<=p[i].y&&p[i].y<=y[b]) on2[k]++;
if(y[a]<p[i].y&&p[i].y<y[b]) on[k]++;
}
if(k <= ) return n;
int M = ;
for(int j = ; j <= k; j++) {
ans = max(ans, l[j]+on2[j]+M);
M = max(M, on[j]-l[j]);
}
}
}
return ans;
}
int main()
{
int kase=;
while(cin>>n&&n)
{
for(int i=;i<n;i++)
{cin>>p[i].x>>p[i].y;
y[i]=p[i].y;
}
printf("Case %d: %d\n",kase++, sove());
} return ;
}