Code Festival Team Relay 2018 : G - バス停と凸包

勉強になりました。
https://beta.atcoder.jp/contests/cf18-relay-open/tasks/relay2018_g

問題

2次元座標上に、3頂点以上が同一直線上に来ないようなN個の点がある。
これらのうち、3個以上を選択したときに、その凸包の面積を考える。
全選択の仕方における面積の総和は2倍すると必ず整数になる。その値をmod 10^9+7で答えよ。

解法

自力で解法にたどり着かなかったので他の回答を見て理解。

頂点を3個以上選択するとあるが、これは0個以上と考えても問題ない。
頂点を2個以下しか選択しない場合、単に面積が0と考えれば解に影響しない。
そうすると、各点を選ぶか選ばないか2^N通りの選択に対する凸包の面積の和を考えればよい。

前提として、まず多角形の面積の求め方を考える。
適当に定点をPと定めよう。多角形の各辺の頂点を、反時計回り順にABとしたとき、三角形PABの符号付面積の総和を求めるとそれが多角形の面積になる。

これを踏まえて元の問題を考える。
上記定点Pは、まぁどこでもよいので原点Oを使うことにする。
N頂点において、ある2点A・Bがなす線分ABが、A→Bが反時計回り順になるような形で凸包になる組み合わせをC通りとする。
すると三角形OABの符号付面積の2C倍(2は問題の要請により倍にするだけ)だけ最終的な解に寄与することになる。

よって、各AB対に対しCの数を求め、OABの符号付面積の2C倍の総和を求める問題と言い換えることができた。
A,Bを総当たりするとすると、Cを高速に求めなければいけない。
これは以下のように求められる。

まず、点Aを固定し、他の頂点を偏角ソートしよう。
次に点Bを偏角ソートした順に総当たりする。
さて、線分ABがA→Bの順で反時計回り順で凸包に包まれる条件を考えると、以下のとおりである。

• Aを中心に、A→Bの向きに対し左側に1個以上凸包に含まれる頂点がある
• Aを中心に、A→Bの向きに対し右側には凸包に含まれる頂点が1個もない

N個中、A→Bの左側にある点をx個とすると、その数は尺取り法の要領で平均O(1)で求められる。
条件を満たすのは、これらのx個のうち1個以上を選択する場合なのでC=2^x-1と考えることができる。

あとはAも総当たりすればよく、全体ではO(N^2*logN)で求めることができる。

int N;
int X[2020],Y[2020];
ll mo=1000000007;
ll p2[2020];

ll cr(int a,int b) {
	ll ret=1LL*X[a]*Y[b]-1LL*X[b]*Y[a];
	return (ret%mo+mo)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,2001) p2[i+1]=p2[i]*2%mo;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	
	double pi=atan(1)*4;
	ll ret=0;
	FOR(i,N) {
		vector<pair<double,int>> V;
		FOR(j,N) if(i!=j) {
			double d=atan2(Y[j]-Y[i],X[j]-X[i]);
			V.push_back({d,j});
			V.push_back({d+2*pi,j});
		}
		sort(ALL(V));
		for(j=r=0;j<N-1;j++) {
			while(V[r].first<V[j].first+pi) r++;
			(ret+=(p2[r-j-1]+mo-1)*cr(i,V[j].second))%=mo;
		}
		
	}
	
	cout<<ret<<endl;
	
}

まとめ

今回のテクは汎用性も高そうだし覚えておかねば。