论水题与难题的差距：在于一个upper_bound
那么，这题一看就很显然了：因为答案满足二分性质所以我们二分。
然后我们再建造一个二维前缀和，每次判断的时候怎么办呢？
我先以为是贪心：选择以每个点为角落的正方形。后来瞬间构造反例：
—————
丨 · 丨
丨 · 丨
丨· 丨
丨 · 丨
—————
然后考虑枚举：500 * 500， 随便水！
然后狂T不止...
发现在枚举内部我还有枚举，具体来说时间复杂度是：log10000 * 500 * 500 * 500
然后我改用了upper_bound，时间复杂度变为：log10000 * 500 * 500 * log500
然后果然A了！
1 /// poj3179 2 #include <cstdio> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 const int N = 510; 7 8 int a[N], b[N], x[N], y[N], g[N][N], sum[N][N], n, C, tx, ty; 9 10 inline bool check(int k) { 11 //printf("check:%d ", k); 12 int ans = 0; 13 for(int i = 1; i <= tx; i++) { 14 for(int j = 1; j <= ty; j++) { 15 int ii = upper_bound(x + i, x + tx + 1, x[i] + k) - x - 1; 16 int jj = upper_bound(y + j, y + ty + 1, y[j] + k) - y - 1; 17 /// 就是这里！ 18 //printf("%d %d %d %d ", i, j, ii, jj); 19 ans = max(ans, sum[ii][jj] - sum[ii][j - 1] - sum[i - 1][jj] + sum[i - 1][j - 1]); 20 if(ans >= C) return 1; 21 //printf("ans=%d ", ans); 22 //ii = i; jj = j; 23 //while(ii >= 0 && x[ii] - x[i] ) 24 } 25 } 26 //printf("%d ", ans); 27 return ans >= C; 28 } 29 30 int main() { 31 int m = -1; 32 scanf("%d%d", &C, &n); 33 for(int i = 1; i <= n; i++) { 34 scanf("%d%d", &a[i], &b[i]); 35 x[i] = a[i]; 36 y[i] = b[i]; 37 m = max(m, x[i]); 38 m = max(m, y[i]); 39 } 40 sort(x + 1, x + n + 1); 41 sort(y + 1, y + n + 1); 42 for(int i = 1; i <= n; i++) { 43 if(x[i] != x[i - 1]) { 44 x[++tx] = x[i]; 45 } 46 if(y[i] != y[i - 1]) { 47 y[++ty] = y[i]; 48 } 49 } 50 for(int i = 1; i <= n; i++) { 51 int px = lower_bound(x + 1, x + tx + 1, a[i]) - x; 52 int py = lower_bound(y + 1, y + ty + 1, b[i]) - y; 53 g[px][py]++; 54 } 55 for(int i = 1; i <= tx; i++) { 56 for(int j = 1; j <= ty; j++) { 57 sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + g[i][j]; 58 } 59 } 60 int l = 0, r = m, mid; 61 while(l < r) { 62 mid = (l + r) >> 1; 63 if(check(mid)) { 64 r = mid; 65 } 66 else l = mid + 1; 67 } 68 printf("%d", r + 1); 69 return 0; 70 }
小细节：1 * 1的方框边长是0，n * n的方框边长是n - 1
所以我最后输出时 + 1