Codeforces #736 Div1 : D1. Gregor and the Odd Cows (Easy)

こっちは何とか解けた。
https://codeforces.com/contest/1548/problem/D1

問題

2次元座標上のN個の点が与えられる。
それぞれX,Y座標は偶数である。

ここから3点選んだ時、内部の格子点の個数が奇数なのは何通りか。

解法

3点のindex i＜j＜kを選ぶとき、kを総当たりしながら残り2点i,jが何通りあるかを考える。
この際、i,j,kを総当たりするとO(N^3)かかるのでi,jの総当たりをやめる。

ピックの定理を考えると、結局iとjのX座標・Y座標を4で割った余りと、i-k及びi-jを結んだ辺上の格子点の数を4で割った余りが定まると、三角形内の格子点の偶奇が定まる。
そこで、まずk未満のindex lについて、上記3値で個数を分類しよう。こうすると各点は4^3通りに分類できる。
そうすれば、kに対し残り2点は(4^6)パターンだけ総当たりすればよく、4^6＜NなのでこれはO(N^2)に収まる。

int N;
int X[10101],Y[10101];
int C[4][4][4];
int R[6060][6060];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(x,N) FOR(y,N) R[x][y]=gcd(abs(X[x]-X[y]),abs(Y[x]-Y[y]))%4;
	
	ll p3=0,p1=0;
	FOR(x,N) {
		X[x]%=4;
		Y[x]%=4;
		ZERO(C);
		FOR(y,N) if(x!=y) C[X[y]%4][Y[y]%4][R[x][y]]++;
			
		int x1,y1,b1,x2,y2,b2;
		FOR(x1,4) FOR(y1,4) FOR(b1,4) FOR(x2,4) FOR(y2,4) FOR(b2,4) {
			ll pat=0;
			if(x1==x2&&y1==y2&&b1==b2) {
				pat=C[x1][y1][b1]*(C[x2][y2][b2]-1);
			}
			else {
				pat=C[x1][y1][b1]*(C[x2][y2][b2]);
			}
			if(x1%2!=x2%2) continue;
			if(y1%2!=y2%2) continue;
			int b3;
			if(x1==x2&&y1==y2) b3=0;
			else b3=2;
			
			int bp=(b1+b2+b3)%4;
			int a=abs(X[x]*y1-Y[x]*x1+x1*y2-y1*x2+x2*Y[x]-y2*X[x])%4;
			
			if(a==bp) {
				if(b1%2==0&&b2%2==0) p3+=pat;
				else p1+=pat;
			}
		}
	}
	
	cout<<(p3/3+p1)/2<<endl;
	
}

まとめ

本番ギリギリまでかかってるな…。