Codeforces #299 Div1 C. Tavas and Pashmaks

問題設定がシンプルながら結構悩む問題。
http://codeforces.com/contest/536/problem/C

問題

水泳の距離がSメートル、ランニングの距離がRメートルのバイアスロンがあったとする。
ここでN人の泳ぐ速さs[i]と走る速さr[i]が与えられる。
SとRの具体的な値は不明だが、どちらも0より大きな実数であることがわかっている。

N人のうち、水泳とランニングの合計時間の短い順に順位を付けるとき、(同着含め)1位になりうる人を列挙せよ。

解法

Editorialを参考に解答。

各人のかかる時間T[i]はである。

(S,R)は正の任意の向きのベクトルを取れるので、T[i]が最小になるということは結局T[i]がを２次元座標上でプロットした際、凸包の下半分を構成することと同義である。
よっての凸包の下半分を求めればよい。

注意点として、今回の問題は同着1位も対象となるため、凸包の頂点だけじゃなく凸包の辺上の人も選ばなければならない点に注意。

const double EPS=1e-20;

template<class C> C veccross(pair<C,C> p1,pair<C,C> p2,pair<C,C> p3) {
	p3.first-=p1.first;p2.first-=p1.first;
	p3.second-=p1.second;p2.second-=p1.second;
	return p3.first*p2.second-p2.first*p3.second;
}

template<class C> vector<int> convex_hull(vector< pair<C, C> >& vp) {
	vector<pair<pair<C, C>, int> > sorted;
	vector<int> res;
	int i,k=0,rb;
	
	if(vp.size()<=2) {
		if(vp.size()>=1) res.push_back(0);
		if(vp.size()>=2 && vp[0]!=vp[1]) res.push_back(1);
		return res;
	}
	
	FOR(i,vp.size()) sorted.push_back(make_pair(vp[i],i));
	sort(sorted.begin(),sorted.end());
	reverse(sorted.begin(),sorted.end());
	
	res.resize(vp.size()*2);
	FOR(i,vp.size()) {
		while(k>1 && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=-EPS) k--;
		res[k++]=sorted[i].second;
	}
	res.resize(k);
	return res;
}

int N;
int S[303030],T[303030];
int ma[11000];
multiset<int> SS[10100];
vector<int> R;

void solve() {
	int i,j,k,l,r,x,y,s;
	
	cin>>N;
	FOR(i,N) {
		cin>>S[i]>>T[i];
		if(ma[S[i]]<T[i]) ma[S[i]]=T[i],SS[S[i]].clear();
		if(ma[S[i]]==T[i]) SS[S[i]].insert(i+1);
	}
	
	vector<pair<double,double> > V;
	y=-1;
	for(s=10000;s>=1;s--) if(ma[s]>0 && (y==-1 || ma[s]>ma[y])) V.push_back(make_pair(1.0/s,1.0/ma[s])), y=s;
	
	vector<int> RR=convex_hull(V);
	FORR(r,RR) FORR(r2,SS[(int)floor(1.0/V[r].first+0.1)]) R.push_back(r2);
	sort(R.begin(),R.end());
	
	FORR(r,R) _P("%d ",r);
	_P("\n");
}

まとめ

convex hull trickを使うことは本番中も推測できたが、ほんとに凸包を愚直に求めればいいとは気付かなかった。