kmjp's blog

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

Hello 2020 : E. New Year and Castle Construction

このコンテストの並び、いつもムーンサイドを思い出す。
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;
}

まとめ

ハロー!そして…グッドバイ!
あの効果音ちょっと怖いよね。