LA 3695 Distant Galaxy

https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=1696
　　今天还做回以前做过的一道题。
　　这题主要是离散化，然后将点的个数转化为前缀和。
View Code
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <vector>
 6 #include <map>
 7 
 8 using namespace std;
 9 typedef vector<int> VI;
10 
11 #define REP(i, n) for (int i = 0; i < (n); i++)
12 #define REP_1(i, n) for (int i = 1; i <= (n); i++)
13 #define INC(i, a, b) for (int i = (a); i <= (b); i++)
14 #define DEC(i, a, b) for (int i = (a); i >= (b); i--)
15 #define PB push_back
16 #define _clr(x) memset(x, 0, sizeof(x))
17 #define SZ(x) ((int) (x).size())
18 #define ALL(x) (x).begin(), (x).end()
19 
20 const int N = 111;
21 VI X, Y;
22 map<int, int> NX, NY;
23 int x[N], y[N];
24 int mat[N][N], preSum[N][N];
25 
26 void input(int n) {
27     NX.clear();
28     NY.clear();
29     X.clear();
30     Y.clear();
31     REP(i, n) {
32         cin >> x[i] >> y[i];
33         X.PB(x[i]);
34         Y.PB(y[i]);
35     }
36     sort(ALL(X));
37     sort(ALL(Y));
38     int t = unique(ALL(X)) - X.begin();
39     while (SZ(X) > t) X.pop_back();
40     REP(i, t) {
41         NX[X[i]] = i + 1;
42     }
43     t = unique(ALL(Y)) - Y.begin();
44     while (SZ(Y) > t) Y.pop_back();
45     REP(i, t) {
46         NY[Y[i]] = i + 1;
47     }
48     _clr(mat);
49     REP(i, n) {
50         mat[NX[x[i]]][NY[y[i]]] = 1;
51     }
52 //    REP_1(i, SZ(X)) {
53 //        REP_1(j, SZ(Y)) {
54 //            cout << mat[i][j];
55 //        }
56 //        cout << endl;
57 //    }
58 }
59 
60 int work() {
61     int nx = SZ(X), ny = SZ(Y), mx = 0;
62     if (nx <= 1 || ny <= 1) return max(SZ(X), SZ(Y));
63     REP_1(i, nx) {
64         REP_1(j, ny) {
65             preSum[i][j] = preSum[i - 1][j] + mat[i][j];
66         }
67     }
68 //    REP_1(i, nx) {
69 //        REP_1(j, ny) {
70 //            cout << preSum[i][j];
71 //        }
72 //        cout << endl;
73 //    }
74     int sum, mn;
75     REP_1(x1, nx) {
76         INC(x2, x1 + 1, nx) {
77             sum = 0;
78             mn = 999999;
79             REP_1(y, ny) {
80                 mx = max(mx, sum + preSum[x2][y] - preSum[x1 - 1][y] - mn);
81                 mn = min(mn, sum - preSum[x2 - 1][y] + preSum[x1][y]);
82                 sum += mat[x1][y] + mat[x2][y];
83             }
84         }
85     }
86     return mx;
87 }
88 
89 int main() {
90 //    freopen("in", "r", stdin);
91     int n, cas = 1;
92     while (cin >> n && n) {
93         input(n);
94         cout << "Case " << cas++ << ": " << work() << endl;
95     }
96     return 0;
97 }
——written by Lyon