题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3962
这个玩意，貌似可以暴力？
预处理出斜着的线上的点有多少，这样在暴力转移的时候，可以做到O(1)
然后就是写代码的事情了，然而写了两个小时了，没写出来QAQ
弃疗………..
—– 2016.9.6 更新 —–
耐着性子码完了代码
为什么觉得线段求交点常数大？
为什么要作死直接分类讨论 (╯‵□′)╯︵┻━┻
#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
const int N = 1000+9;
int n,m,q,sz,head[N],vout,X,Y;
int mat[N][N],f[2][N][N];
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}
inline void prework(){
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) f[0][i][j] = f[0][i-1][j-1] + mat[i][j];
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) f[1][i][j] = f[1][i+1][j-1] + mat[i][j];
}
inline int pro(int x1, int y1, int x2, int y2, int t) {
int ret = 0;
if (!t) {
x2--; y2--;
if (x1 < 1 || y1 < 1) ret += 0;
else if (x1 <= n && y1 <= m) ret += f[t][x1][y1];
else if (x1 > n) ret += (y1-(x1-n)<=m && y1-(x1-n)>=1)? f[t][n][y1-(x1-n)]: 0;
else ret += (1<=x1-(y1-m) && x1-(y1-m)<=n)? f[t][x1-(y1-m)][m]: 0;
if (x2 < 1 || y2 < 1) ret -= 0;
else if (x2 <= n && y2 <= m) ret -= f[t][x2][y2];
else if (x2 > n) ret -= (y2-(x2-n)<=m && y2-(x2-n)>=1)? f[t][n][y2-(x2-n)]: 0;
else ret -= (1<=x2-(y2-m) && x2-(y2-m)<=n)? f[t][m][2-(y2-m)]: 0;
} else {
x2++; y2--;
if (x1 > n || y1 < 1) ret += 0;
else if (x1 >= 1 && y1 <= m) ret += f[t][x1][y1];
else if (x1 < 1) ret += (y1-(1-x1)>=1 && y1-(1-x1)<=m)? f[t][1][y1-(1-x1)]: 0;
else ret += (x1+(y1-m)>=1 && x1+(y1-m)<=n)? f[t][x1 + (y1 - m)][m]: 0;
if (x2 > n || y2 < 1) ret -= 0;
else if (x2 >= 1 && y2 <= m) ret -= f[t][x2][y2];
else if (x2 < 1) ret -= (y2-(1-x2)>=1 && y2-(1-x2)<=m)? f[t][1][y2 -(1-x2)]: 0;
else ret -= (1<=x2+(y2-m) && x2+(y2-m)<=n)? f[t][x2+(y2-m)][m]: 0;
} return ret;
}
inline void solve(int lim){
vout = 0; X = 1; Y = 1;
for (int j=1;j<=m;j++) for (int i=1;i<=n;i++)
if (i + j > lim + 2) break;
else vout += mat[i][j];
head[1] = vout; int tmp = vout;
for (int j=1;j<=m;j++) {
for (int i=1;i<n;i++) {
tmp += pro(i+lim+1,j,i+1,j-lim,0); // ¨J
tmp -= pro(i,j+lim,i-lim,j,0); // ¨L
tmp += pro(i+1,j+lim,i+lim+1,j,1); // ¨K
tmp -= pro(i-lim,j,i,j-lim,1); // ¨I
if (i + lim + 1 <= n) tmp -= mat[i+lim+1][j];
if (i - lim >= 1) tmp += mat[i-lim][j];
if (tmp > vout) vout = tmp, X = i+1, Y = j;
}
if (j < m) {
tmp = head[j];
tmp += pro(1,j+lim+1,1+lim,j+1,1);//¨K
tmp += pro(1,j+lim+1,1-lim,j+1,0);//¨L
tmp -= pro(1+lim,j,1,j-lim,0);//¨J
tmp -= pro(1-lim,j,1,j-lim,1);//¨I
if (j + lim + 1 <= m) tmp -= mat[1][j+lim+1];
if (j - lim >= 1) tmp += mat[1][j-lim];
if (tmp > vout) vout = tmp, X = 1, Y = j+1;
head[j+1] = tmp;
}
}
}
inline void init(int w){
memset(f,0,sizeof(f));
memset(mat,0,sizeof(mat));
printf("Case %d:\n",w);
}
int main(){
for (int T=1;scanf("%d%d",&n,&m) && n && m;T++) {
init(T); sz = read(); q = read();
for (int i=1,x,y;i<=sz;i++) x = read(), y = read(), mat[x][y]++;
prework();
for (int k=1;k<=q;k++) {
solve(min(m+n,read()));
printf("%d (%d,%d)\n",vout,X,Y);
}
}
return 0;
}
然而DZY告诉我们，这货可以变成正方形？
参见：http://dzy493941464.is-programmer.com/posts/86498.html
仔细想了一想：我们可以通过将整个图旋转45°，然后重新编号，然后就变成了正方形？
然后就是很常规的滑动窗口了？
—– UPD 2016.6.9 —–
坐标旋转的代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2000+9;
int n,k,q,mat[N][N],sta[N],sum[N][N],MX;
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
#define SUM(x,y) sum[max(0,min(x,MX))][max(0,min(y,MX))]
inline void solve(int lim) { int vout = 0;
for (int j=1;j<=n;j++) for (int i=1,x,y;i<=n;i++) x = sta[i]-j+1, y = i+j-1,
vout = max(vout, SUM(x+lim,y+lim) + SUM(x-lim-1,y-lim-1) - SUM(x+lim,y-lim-1) - SUM(x-lim-1,y+lim));
printf("%d\n",vout);
}
int main(){
n = read(); k = read(); q = read(); MX = n * 2 - 1;
sta[1] = n; for (int i=2;i<=n;i++) sta[i] = sta[i-1] + 1;
for (int i=n+1;i<=n*2-1;i++) sta[i] = sta[i-1] - 1;
for (int i=k,x,y;i;--i) x = read(), y = read(), mat[sta[x]-y+1][x+y-1] = 1;
for (int j=1;j<=MX;j++) for (int i=1;i<=MX;i++) sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + mat[i][j];
for (int i=1;i<=q;i++) solve(read());
return 0;
}
