Codeforces #335 Div1 C. Freelancer's Dreams

これは本番全く思いつかなかったので、解けなくてもしょうがないかな…。
http://codeforces.com/contest/605/problem/C

問題

プレイヤーのスキルは2つのパラメータからなる。
初期状態のパラメータは(0,0)である。

ここでN個のタスクがあり、それぞれ1日間行うと2つのパラメータを(A[i],B[i])上昇できる。
なお、タスクの実行は小数時間でも良い。

プレイヤーのパラメータがそれぞれp,q以上になる最小日数を求めよ。

解法

2次元座標において、原点と(A[i],B[i])全ての点から構成される凸包を考える。
この凸包の内部は、1日で上昇できるパラメータの範囲を示す。
よってこの凸包をx倍して(p,q)の右上に来る点が現れるような最小のxを求める。

このxの求め方は以下どちらでも良い。

• 直接計算で求める。以下の2日の最小値を取ろう。
  • 1種類のタスクだけを使った場合max_i(max(p/A[i],q/B[i])日かかる。
  • 複数種類のタスクを使う場合、凸包のうち(0,0)と(p,q)を結んだ直線、すなわちy=(q/p)xと凸包の交点を求めよう。
    • この交点は2つのパラメータをp:qの比率で進めたときに、1日で得られる最大パラメータを示す。よって原点から(p,q)までの距離を、原点からこの交点までの距離で割れば日数が求まる。
• 二分探索で求める。
  • 1種類のタスクだけを使った場合A[i]*x≧pかつB[i]*x≧qであるxがあれば、x日で条件を満たせる。
  • 複数種類のタスクを使う場合、凸包をx倍拡大した図形に(p,q)が含まれれば、x日で条件を満たせる。

ll N,P,Q;
vector<pair<ll,ll>> V;
ll A[101010],B[101010];

const ll EPS=0;
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());
	
	res.resize(vp.size()*2);
	/* bottom */
	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;
	}
	/* top */
	for(rb=k, i=vp.size()-2;i>=0;i--) {
		while(k>rb && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=-EPS) k--;
		res[k++]=sorted[i].second;
	}
	res.resize(k-1);
	return res;
}

double pace(int x,int y) {
	double t=(P*B[x]-Q*A[x])/(1.0*(A[y]*Q-P*B[y]));
	double tt=1+t;
	double dx=A[x]+t*A[y];
	double dy=B[x]+t*B[y];
	return sqrt(dx*dx+dy*dy)/tt;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	double ret=1e9;
	
	cin>>N>>P>>Q;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		ret=min(ret,max(P/(1.0*A[i]),Q/(1.0*B[i])));
		V.push_back({A[i],B[i]});
	}
	auto VS=convex_hull(V);
	
	FOR(i,VS.size()) if(((A[VS[i]]*Q-B[VS[i]]*P)<0)^((A[VS[(i+1)%VS.size()]]*Q-B[VS[(i+1)%VS.size()]]*P)<0)) {
		ret=min(ret,sqrt(P*P+Q*Q)/pace(VS[i],VS[(i+1)%VS.size()]));
	}
	
	_P("%.12lf\n",ret);
	
}

まとめ

凸包に気づいてしまえばあっさり。まぁ気づかなかったんだけどね。