解題區/解題區 - UVa

UVa 1382 - Distant Galaxy

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給平面上 N 個點，找一個最大矩形，使得矩形邊上有最多點個數。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
10 
2 3 
9 2 
7 4 
3 4 
5 7 
1 5 
10 4 
10 6 
11 4 
4 6 
0

Sample Output

1
Case 1: 7

Solution

UVa 1382

先離散化處理，將所有點放置在 grid[100][100] 內。

接著窮舉上下兩條平行線，由左而右開始掃描，邊緣的個數為 V[U1] + V[U2] + H[R] - V[U3] + V[U4] + H[L]，掃描時維護 V[U3] + V[U4] - H[L] 的最小值。

特別小心矩形的四個頂點的排容，上述的公式仍然不太夠。由於題目沒有特別要求正面積矩形，必須考慮共線上最多的點個數。

效率 O(n^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h> 
#include <map>
#include <algorithm>
using namespace std;
int main() {
    int n, x[128], y[128];
    int cases = 0;
    while (scanf("%d", &n) == 1 && n) {
        map<int, int> Rx, Ry;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &x[i], &y[i]);
            Rx[x[i]] = 0, Ry[y[i]] = 0;
        }
        
        int size, R, C;
        size = 0;
        for (map<int, int>::iterator it = Rx.begin();
            it != Rx.end(); it++) {
            it->second = size++;
        }
        R = size;
        size = 0;
        for (map<int, int>::iterator it = Ry.begin();
            it != Ry.end(); it++) {
            it->second = size++;
        }
        C = size;
        
        int g[128][128] = {}, ret = 0;
        for (int i = 0; i < n; i++) {
            int r, c;
            r = Rx[x[i]], c = Ry[y[i]];
            g[r][c]++;
        }
        
        for (int i = 0; i < R; i++) {
            int sum[128] = {}, s1, s2, mn;
            for (int j = i; j < R; j++) {
                s1 = s2 = 0, mn = 0;
                for (int k = 0; k < C; k++) {
//					printf("[%d %d] %d\n", i, j, k);
                    sum[k] += g[j][k];
                    s1 += g[i][k], s2 += g[j][k];
                    if (i != j) {
//						printf("%d %d %d %d = %d\n", s1, s2, mn, sum[k], s1 + s2 - mn + sum[k]);
                        ret = max(ret, s1 + s2 - mn + sum[k] - g[i][k] - g[j][k]);
                        mn = min(mn, s1 + s2 - sum[k]);
                    }
                }
            }
        }
        
        for (int i = 0; i < R; i++) {
            int sum = 0;
            for (int j = 0; j < C; j++)
                sum += g[i][j];
            ret = max(ret, sum);
        }
        
        for (int i = 0; i < C; i++) {
            int sum = 0;
            for (int j = 0; j < R; j++)
                sum += g[j][i];
            ret = max(ret, sum);
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}
/*
10 
2 3 
9 2 
7 4 
3 4 
5 7 
1 5 
10 4 
10 6 
11 4 
4 6 
3
1 1
2 1
3 1
3
1 1
1 2
1 3
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
*/