勉強になりました。
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; }
まとめ
今回のテクは汎用性も高そうだし覚えておかねば。