kmjp's blog

競技プログラミング参加記です

AtCoder ABC #202 (エイシングプログラミングコンテスト2021) : F - Integer Convex Hull

ARC

参加が遅れたので間に合わず。
https://atcoder.jp/contests/abc202/tasks/abc202_f

問題

2次元座標上で、N個の点が与えられる。
この点の集合の部分集合の選び方のうち、凸包の面積が整数になるものは何通りか。

解法

まず整数云々だが、格子点を結んで作る多角形の面積は整数か(整数+1/2)の形にしかならないので、面積を2倍した値の偶奇を管理することで考えればよい。
あとは、凸法を列挙していく問題を考える。

前処理として、3点を選んだ時、内部にある他の点の数を列挙しておこう。
これは後で凸法を徐々に広げて行く際、この3点からなる三角形を追加した場合、その内部の点は選んでも選ばなくても凸法の形状に関係ないので、これらの点がk個あるなら点の選び方は2^k通りあることになる。

あとは、凸法を列挙していく。事前に点を昇順にソートしておく。
凸法のうち一番頂点番号が小さい点をLとし、以下を考える。

  • up(L,x,y,b) := 凸法の下端がL-yを結ぶ辺で、その上に他の点がある。yと隣接するLの反対側の点はx。bはここまでの面積の2倍の偶奇。
  • down(L,x,y,b) := 凸法の上端がL-yを結ぶ辺で、その下に他の点がある。yと隣接するLの反対側の点はx。bはここまでの面積の2倍の偶奇。

(up(L,*,y,b)*down(L,*,y,b)-1)が、Lを最小頂点番号、yを最大頂点番号とし、面積が整数となる凸法を構成する頂点集合の数となる(1引くのは、面積が0のケースを除くため)
あとは頂点zを総当たりし、up(L,x,y,b)→up(L,y,z,*)やdown(L,x,y,b)→down(L,y,z,*)の遷移を列挙しよう。その際は、前処理で求めた内部の点の選び方の分を忘れないようにする。

int N;
pair<int,int> P[101];
int X[101],Y[101];
const ll mo=1000000007;

ll num[88][88][88];
int S[88][88][88];
int A[88][88];
ll up[80][80][2];
ll down[80][80][2];


int side(int a,int b,int c) {
	ll Xab=X[b]-X[a];
	ll Yab=Y[b]-Y[a];
	ll Xac=X[c]-X[a];
	ll Yac=Y[c]-Y[a];
	
	return Xab*Yac>Yab*Xac;
}

ll area(int a,int b) {
	ll S=X[a]*Y[b]-Y[a]*X[b];
	return abs(S)%2;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i].first>>P[i].second;
	}
	sort(P,P+N);
	FOR(i,N) X[i]=P[i].first, Y[i]=P[i].second;
	
	FOR(i,N) FOR(j,N) A[i][j]=area(i,j);
	FOR(i,N) FOR(j,N) FOR(k,N) S[i][j][k]=side(i,j,k);
	FOR(i,N) FOR(j,N) FOR(k,N) {
		if(!S[i][j][k]) continue;
		num[i][j][k]=1;
		FOR(x,N) {
			if(S[i][j][x]==0) continue;
			if(S[j][k][x]==0) continue;
			if(S[k][i][x]==0) continue;
			(num[i][j][k]*=2)%=mo;
		}
	}
	
	ll ret=0;
	FOR(i,N) {
		ZERO(up);
		ZERO(down);
		for(x=i+1;x<N;x++) up[i][x][0]=down[i][x][0]=1;
		for(x=i;x<N;x++) {
			for(y=x+1;y<N;y++) for(k=y+1;k<N;k++) {
				ll w=num[i][y][k]+num[i][k][y];
				int a=A[i][y]^A[y][k]^A[k][i];
				if(S[x][y][k]) {
					(up[y][k][a^0]+=w*up[x][y][0])%=mo;
					(up[y][k][a^1]+=w*up[x][y][1])%=mo;
				}
				else {
					(down[y][k][a^0]+=w*down[x][y][0])%=mo;
					(down[y][k][a^1]+=w*down[x][y][1])%=mo;
				}
			}
			if(x>i) {
				ll U[2]={0,0},D[2]={0,0};
				FOR(y,N) {
					(U[0]+=up[y][x][0])%=mo;
					(U[1]+=up[y][x][1])%=mo;
					(D[0]+=down[y][x][0])%=mo;
					(D[1]+=down[y][x][1])%=mo;
				}
				
				(ret+=U[0]*D[0]+mo-1+U[1]*D[1])%=mo;
			}
		}
		
	}
	cout<<ret%mo<<endl;
}

まとめ

途中までO(N^5)解をやってたけど、定数倍最適化で時間的には間に合いそう。