Codeforces #328 Div2 E. BCPC

やりたいことはわかりやすいが、地味に苦戦した。
http://codeforces.com/contest/592/problem/E

問題

問題文が分かりにくいので大幅に要約。
N人のパラメータ(R[i],W[i])が与えられる。(元問題文にあるC,Dは適用済みとする)

i番の人がj番を凌駕するとは、R[i]*W[j]＞R[j]*W[i]であることを意味する。
ここでN人中3人組i,j,kを考える。i番がj番を凌駕し、j番がk番を凌駕し、k番がi番を凌駕するような関係にある3人組は何通り作れるか。

解法

R[i]*W[j]＞R[j]*W[i]よりR[i]*W[j]-R[j]*W[i]＞0。
これは(R[i],W[i])をそのまま2次元座標上にプロットしたとき、原点から見てj番がi番の左側にあることを意味する。
また3人が互いに凌駕する関係を言い換えると、結局原点を囲む3点の組を選ぶ問題と見なすことができる。

まず入力値を偏角ソートする。
偏角の小さい順にi,j,kを取るとして、iを総当たりする。
iが決まると、jはOiとOjの角度がは0と180度の間に含まれる頂点の範囲で選択できる。
また、iとjが決まると、kはOjとOkの角度が180度未満かつOiとOkの偏角が180度を超える範囲から求めることができる。

F(x)を偏角が(xの偏角+180度以下)の頂点数、G(x)を偏角が(xの偏角+180度未満)の頂点数とする。
F(x)とG(x)の累積和を先に求めておくと、上記j,kの数をO(1)で計算できるようになる。

この問題では同じ座標の点は複数回登場しないが、同じ偏角の点は複数回登場しうるため、そこを数え間違えないように注意すること。
180度未満・以上・以下・超えるをちゃんと使い分けないとWAする。

int N,C,D;
vector<pair<ll,ll>> V;
ll num[456789],num2[456789];
ll S[456789];
ll ret;
int same[456789];

bool comp(pair<ll,ll> &L,pair<ll,ll> &R) {
	if(L==R) return 0;
	if(L.second==0 && L.first>0) return 1;
	if(R.second==0 && R.first>0) return 0;
	if(L.second>0 && R.second<=0) return 1;
	if(R.second>0 && L.second<=0) return 0;
	if(L.second>=0 && R.second<0) return 1;
	if(R.second>=0 && L.second<0) return 0;
	return L.first*R.second-L.second*R.first>0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>C>>D;
	
	FOR(i,N) {
		cin>>x>>y;
		x-=C;
		y-=D;
		int g=__gcd(abs(x),abs(y));
		V.push_back({x/g,y/g});
	}
	
	sort(ALL(V),comp);
	FOR(i,N) {
		num[i]=max(i+1LL,(i)?num[i-1]:0);
		if(V[i].second<0 || (V[i].second==0&&V[i].first<0)) num[i]=N;
		else {
			pair<ll,ll> rev={-V[i].first,-V[i].second};
			while(num[i]<N && comp(V[num[i]],rev)) num[i]++;
		}
		num2[i]=max(num[i],(i)?num2[i-1]:0);
		while(num2[i]<N && V[num2[i]].first==-V[i].first && V[num2[i]].second==-V[i].second) num2[i]++;
		
		S[i]=((i)?S[i-1]:0)+num[i];
	}
	for(i=N-1;i>=0;i--) {
		if(i<N-1&&V[i]==V[i+1]) same[i]=same[i+1];
		else same[i]=i;
	}
	
	FOR(x,N) ret+=(S[num[x]-1]-S[same[x]])-num2[same[x]]*(num[same[x]]-1-same[x]);
	cout<<ret<<endl;
}

まとめ

今回問題文難しすぎないですかね…。