このコンテストの並び、いつもムーンサイドを思い出す。
https://codeforces.com/contest/1284/problem/E
問題
2次元座標上にN個の点が与えられる。
3点以上が互いに同一直前上に乗ることはない。
点pに対し、f(p)とはN個の点のうち4点を選んだ時、それらの凸包にpが含まれるような選び方の組み合わせとする。
各点vにおけるf(v)の和を求めよ。
解法
4点というが、結局pを囲う3点が決まればあと1点はその外側なら何でもよい。
pを総当たりしつつその周辺の点を偏角ソートし、累積和を使いながら数え上げて行こう。
int N; ll X[3030],Y[3030]; ll tar[60600],tar2[60600]; ll star[60600],star2[60600]; ll sum[6060]; void solve() { int i,j,k,l,r,x,y; long double pi=atan((long double)1)*4; cin>>N; FOR(i,N) cin>>X[i]>>Y[i]; ll ret=0; FOR(i,N) { vector<long double> V; FOR(j,N) if(i!=j) { long double a=atan2((long double)Y[j]-Y[i],(long double)X[j]-X[i]); V.push_back(a); V.push_back(2*pi+a); V.push_back(4*pi+a); } sort(ALL(V)); int R=0; FOR(j,2*(N-1)) { while(V[R+1]-V[j]<=pi) R++; tar[j]=R; tar2[j]=R*R; star[j]=tar[j]; star2[j]=tar2[j]; if(j) { star[j]+=star[j-1]; star2[j]+=star2[j-1]; } } FOR(j,N-1) { x=tar[j]; ret+=((star2[x]-star2[j])-2*tar[j]*(star[x]-star[j])+(x-j)*tar2[j]-(star[x]-star[j])+(x-j)*tar[j])/2; } } cout<<ret<<endl; }
まとめ
ハロー!そして…グッドバイ!
あの効果音ちょっと怖いよね。