yukicoder No.325 マンハッタン距離2

問題はこちら
No.325 マンハッタン距離2 - yukicoder

ショートコード以前に、普通に通すだけでめちゃくちゃ難しかった。

与えられた長方形をに属する格子点を、各象限ごとに求めて合計するという方針で考えた。このとき、軸上の点を重複カウントしないように、図のようにした。

（原点は必要なら後で足す）
で、例えば上図の場合は、赤枠部分にあって条件を満たすものをカウントするのは適当にやれば出来るのだけど、元の長方形が軸や原点を含まないときに上手く扱うのが難しい。
そういうことで、「やっぱ軸上も数える方が自然だよね」ということで、各部分について求める際に、全体を適当に平行移動することにした。

この平行移動は「長方形の左端や下端がもし第一象限の内部にあれば軸上に移動する」「ただし下方向へは必ず1以上動かす」となる。
このように平行移動した時の右上の頂点の座標を(x,y)とすれば、x,yがともに0以上のときにかぎりこの領域は空でなく、題意を満たすような点を探すことに意味があることに注意する。
さて、このような領域にあって、原点からのマンハッタン距離がz以下であるものを考える（平行移動した際に、dも動いているので別変数で表している）

例えばx+y<zの場合は上図のような4つの直角二等辺三角形の切り貼りで表すことが出来る
三角形の一辺の長さがnのとき、その(境界を含む)内部にある格子点の数をf(n)とおくと、これは明らかにn*(n+1)/2で求められるので、上図の場合はf(z+1)-f(z-x)-f(z-y)+f(z-x-y-1)で求められる。
ここではx+y<zの場合のみを挙げたが、n<0のときf(n)=0と定めると、他の場合でもこれが成立していることが確かめられる。
ということでこれを頑張って実装

long m;x1,x2,y1,y2,d;
#define max(p,q)(p>q?p:q)
#define f(n)(n>0?(n)*(n+1)/2:0)
void g(p,q,r,s){
//(p,q)が右上の点、(r,s)が左下の点のとき
//1つ目の図の赤色部分にあって条件を満たすものの個数を求める
	long x,y,z;
	x=p-max(r,0);
	y=q-max(s,1);
	//平行移動
	z=d-max(r,0)-max(s,1);
	//移動した分だけdも変わる
	m+=x>=0&y>=0?f(z+1)-f(z-y)-f(z-x)+f(z-x-y-1):0;
	//条件を満たす個数を足す
}
int main(){
	scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&d);
	m=x1<=0&x2>=0&y1<=0&y2>=0;
	//原点の分は予め足しておく
	g(x2,y2,x1,y1);
	g(y2,-x1,y1,-x2);
	g(-x1,-y1,-x2,-y2);
	g(-y1,x2,-y2,x1);
	//長方形を回転させることで、全て赤色部分に帰着させる
	printf("%ld",m);
	return 0;
}

gを4回書いているが、これはxi,yiを適当にローテーションさせることでループにより書ける

long m,x,y,z;A,B,C,D,d;
#define f(n)(n>0?(n)*~(n)/2:0)
main(i){
	scanf("%d%d%d%d%d",&A,&B,&C,&D,&d);
	for(m=A<=0&C>=0&B<=0&D>=0;++i<6;x=A,A=B,B=-C,C=D,D=-x)
		z=d-(x=A>0?A:0)-(y=B>1?B:1),
		x=C-x,
		y=D-y,
		m-=x<0|y<0?0:f(z+1)-f(z-y)-f(z-x)+f(z-x-y-1);
	m=!printf("%ld",m);
}

原点を含むかどうかの判定はA*C<=0&B*D<=0でできるが、オーバーフローしないために(AとC)(BとD)でそれぞれ少なくとも一方はlong型にしておく必要がある。
ついでにfの引数に毎回zを書くのはめんどくさいような気がするので、これはfの中にいれてしまう

long x,y,z,m,A,B;C,D,d;
#define f(n)(z>n?(z-n)*~(z-n)/2:0)
main(i){
	scanf("%ld%ld%d%d%d",&A,&B,&C,&D,&d);
	for(m=A*C<=0&B*D<=0;++i<6;x=A,A=B,B=-C,C=D,D=-x)
		z=d-(x=A>0?A:0)-(y=B>1?B:1),
		x=C-x,
		y=D-y,
		m-=x<0|y<0?0:f(-1)-f(y)-f(x)+f((x+y+1));
	m=!printf("%ld",m);
}

さて、真ん中あたりに残ったx=C-x;y=D-y;の2つをx-=C;y-=D;と横着できないだろうか。
こうするとx,yに入る値が正負逆になるので、それにともなってfの引数も逆にすることにすると

long x,y,z,m,A,B;C,D,d;
#define f(n)(n>-z?(z+n)*~(z+n)/2:0)
main(i){
	scanf("%ld%ld%d%d%d",&A,&B,&C,&D,&d);
	for(m=A*C<=0&B*D<=0;++i<6;x=A,A=B,B=-C,C=D,D=-x)
		z=d-(x=A>0?A:0)-(y=B>1?B:1),
		x-=C,
		y-=D,
		m-=x>0|y>0?0:f(1)-f(y)-f(x)+f(x+y-1);
	m=!printf("%ld",m);
}

247B

もうやりたくない

16/07/10追記
まだまだ短縮箇所はたくさん残っていた

#define f(n)(n>-z?(z+n)*~(z+n)/2:0)
#define f(n)(n>-z)*(z+n)*~(z+n)/2
//zの正負を逆にすることによりさらに1B縮む
#define f(n)(n>z)*(n-z)*~(n-z)/2

さらに

m-=x>0|y>0?0:f(1)-f(y)-f(x)+f(x+y-1);
m-=x<1&y<1?f(1)-f(y)-f(x)+f(x+y-1):0;

と書き換えたのち、x<1&y<1をfの中に押し込めることで

#define f(n)(n>z)*(n-z)*~(n-z)/2
m-=x<1&y<1?f(1)-f(y)-f(x)+f(x+y-1):0;

#define f(n)(x<1&y<1&n>z)*(n-z)*~(n-z)/2
m-=f(1)-f(y)-f(x)+f(x+y-1);

2B短縮
最後に、ABCDのローテーションのタイミングを変えることで、xに予めAの値を代入しておき、x=A>0?A:0の部分をx*=A>0とすることで3B短縮

long x,y,z,m,A,B;C,D,d;
#define f(n)(x<1&y<1&n>z)*~(n-z)*(n-z)/2
main(i){
	scanf("%ld%ld%d%d%d",&A,&B,&C,&D,&d);
	for(m=A*C<=0&B*D<=0;++i<6;m-=f(1)-f(y)-f(x)+f(x+y-1))
		x=B,B=-C,C=D,D=-A,A=x,
		z=(x*=A>0)+(y=B>1?B:1)-d,
		x-=C,
		y-=D;
	m=!printf("%ld",m);
}

合計で8B短縮の239B