运用部分枚举的思想，很明显完全枚举点的思想是不可能的。改为枚举上下边界，当确定右边界j后，对左边界i，可以有点数为on[j]+on[i]+(leftu[j]-leftu[i])+leftd[j]-leftd[i]。然后取最大值，on[j]+on[i]+(leftu[j]-leftu[i])+leftd[j]-leftd[i]=(on[j]+leftu[j]+leftd[j])+on[i]-leftu[i]-leftd[i]。维护on[i]-leftu[i]-leftd[i]的最大值。leftu为上边界左该点左边的点数，leftd是下边界的。
注意竖线与横线交点处是否有点。所以维护最大值时应改为on[i]-leftu[i-1]-leftd[i-1];
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring> using namespace std; struct Point{
int x,y;
}P[105];
int y[105],leftu[105],leftd[105],onu[105],ond[105],on[105]; bool cmp(Point a,Point b){
if(a.x<b.x) return true;
return false;
} int gao(int n){
sort(P,P+n,cmp);
sort(y,y+n);
int m=unique(y,y+n)-y;
if(m<=2) return n;
int colk=0;
int res=0;
for(int i=0;i<m;i++){
for(int j=i+1;j<m;j++){
colk=0;
for(int k=0;k<105;k++){
leftu[k]=leftd[k]=on[k]=onu[k]=ond[k]=0;
}
for(int k=0;k<n;k++){
if(colk==0||P[k].x!=P[k-1].x){
on[colk]=onu[colk]-ond[colk]; colk++;
leftu[colk]+=leftu[colk-1];
leftd[colk]+=leftd[colk-1];
}
if(P[k].y==y[j]) leftu[colk]++;
else if(P[k].y==y[i]) leftd[colk]++;
if(P[k].y<=y[i]) ond[colk]++;
if(P[k].y<y[j]) onu[colk]++;
}
on[colk]=onu[colk]-ond[colk]; if(colk<=2) return n;
int tmpmax=on[1]-leftu[0]-leftd[0];
for(int k=2;k<=colk;k++){
res=max(res,on[k]+leftu[k]+leftd[k]+tmpmax);
tmpmax=max(tmpmax,on[k]-leftu[k-1]-leftd[k-1]);
}
} }
return res;
} int main(){
int kase=0,n;
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;
}
int ans=gao(n);
printf("Case %d: %d\n",++kase,ans);
}
return 0;
}