Coffee Central

There is a simple DP that tells you for a query dp[x][y] how many of a given item are in the range from (0,0) to (x,y). It's really quite trivial...just walk the grid, and dp[x][y] = dp[x][y-1] + dp[x-1][y] + location(x,y)? 1 : 0.

This means we can query between any rectangle (x1,y1) (x2,y2) using dp[x2][y2] - dp[x1][y2] - dp[x2][y1] + dp[x1][y1] (inclusion/exclusion). So how does that help us? We have manhattan distance, which forms diamonds, not rectangles!

So rotate the grid 45 degrees first, run the RP on the rotated grid, then perform queries for every location. and choose the biggest one. Grid is only 1000x1000 so fast enough.

import java.awt.Point;
import java.util.*;
public class e {
	Scanner in=new Scanner(System.in);
	public static void main(String[] args) {
		new e().go();
	}
	private void go() {
		int cnum=0;
		while(true){
			cnum++;
			int dx=in.nextInt()+1;
			if(dx==1)break;
			int dy=in.nextInt()+1;
			int n=in.nextInt();
			int q=in.nextInt();
			int[][] dp=new int[dx+dy-1][dx+dy-1];
			for(int i=0;i<n;i++){
				int x=in.nextInt();
				int y=in.nextInt();
				dp[x+y][dy-1+x-y]=1;
			}
			for(int i=1;i<dp.length;i++)for(int j=1;j<dp.length;j++)dp[i][j]+=(dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]);
			System.out.printf("Case %d:\n",cnum);
			for(int i=0;i<q;i++){
				int d=in.nextInt();
				int max=0;
				Point maxLoc=new Point(1,1);
				for(int j=0;j<dp.length;j++){
					for(int k=0;k<dp.length;k++){
						if((k+j)%2==dy%2)continue;
						Point t=new Point(j-(j-k+dy-1)/2,(j-k+dy-1)/2);
						if(t.x<=0||t.y<=0)continue;
						int jup=Math.min(j+d, dp.length-1);
						int jdn=Math.max(j-d-1,0);
						int kup=Math.min(k+d, dp.length-1);
						int kdn=Math.max(k-d-1,0);
						int temp=dp[jup][kup]-dp[jdn][kup]-dp[jup][kdn]+dp[jdn][kdn];
						if(temp>max||(temp==max&&(t.y<maxLoc.y||(t.y==maxLoc.y&&t.x<maxLoc.x)))){
							max=temp;
							maxLoc=t;
						}
					}
				}
				System.out.printf("%d (%d,%d)\n", max,maxLoc.x,maxLoc.y);
			}
		}
	}
}
//Coffee Central
//dp
//rotation
//inclusion exclusion