uvalive3695Distant Galaxy

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #define DEBUG
 5 using namespace std;
 6 struct ZZ{
 7     int x, y;
 8     bool operator < (const ZZ& p) const{
 9         return x<p.x;
10     }
11 };
12 int max(int a, int b){
13     return a>b?a:b;
14 }
15 const int MAXN = 100 + 10;
16 ZZ p[MAXN];
17 int n, m, y[MAXN], on[MAXN], on2[MAXN], zl[MAXN];
18 
19 int solve(){
20     sort(p, p+n);
21     sort(y, y+n);
22     m = unique(y, y+n) - y;
23     if(m<=2) return n;
24     
25     int ans = 0;
26     for(int a=0; a<m; a++){
27         for(int b=a+1; b<m; b++){
28             int ymin = y[a];
29             int ymax = y[b];
30 
31             int k = 0;
32             for(int i=0; i<n; i++){
33                 if(i==0 || p[i].x!=p[i-1].x){
34                     k++;
35                     on[k] = on2[k] = 0;
36                     if(k==0) zl[k] = 0;
37                     else zl[k] = zl[k-1] + on2[k-1] - on[k-1];
38                 }
39                 if(p[i].y>ymin && p[i].y<ymax) on[k]++;
40                 if(p[i].y>=ymin && p[i].y<=ymax) on2[k]++;
41             }
42             if(k<=2) return n;
43 
44             int M = 0;
45             for(int j=1; j<=k; j++){
46                 ans = max(ans, zl[j]+on2[j]+M);
47                 M = max(M, on[j]-zl[j]);
48             }
49         }
50     }
51     return ans;
52 }
53 int main(){
54 #ifndef DEBUG
55     freopen("in.txt", "r", stdin);
56 #endif
57     int cas=0;
58     while(scanf("%d", &n)==1 && n){
59         for(int i=0; i<n; i++){
60             scanf("%d%d", &p[i].x, &p[i].y);
61             y[i]=p[i].y;
62         }
63         printf("Case %d: %d\n", ++cas, solve());
64     }
65     return 0;
66 }