やりたいことはわかりやすいが、地味に苦戦した。
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; }
まとめ
今回問題文難しすぎないですかね…。