AtCoder ABC #139 : F - Engines

これはライブラリの有無で難易度変わるなぁ。
https://atcoder.jp/contests/abc139/tasks/abc139_f

問題

2次元座標において、N個のベクトルが与えられる。
うち任意の部分集合を選んだ時、原点から選んだベクトルに沿って順に移動したあとの原点からの距離の最大値を求めよ。

解法

各ベクトルが張る凸法を順次更新していこう。
具体的には、初期値は(0,0)だけからなる図形を考える。

各ベクトル(x,y)に対し、処理途中の凸法の各点と、その凸法を(x,y)だけずらした点を列挙し、両者合わせた点の凸法を新たな点として更新しよう。
最後に、凸法の各点までの距離を求めればよい。

int N;
ll X[101],Y[101];

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;
}




void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<pair<ll,ll>> V;
	V.push_back({0,0});
	FOR(i,N) {
		cin>>x>>y;
		j=V.size();
		FOR(k,j) V.push_back({V[k].first+x,V[k].second+y});
		
		vector<int> W=convex_hull(V);
		
		vector<pair<ll,ll>> V2;
		FORR(w,W) V2.push_back(V[w]);
		swap(V,V2);
	}
	
	double ma=0;
	FORR(v,V) ma=max(ma,hypot(v.first,v.second));
	_P("%.12lf\n",ma);
}

まとめ

方針が立てば、あとはライブラリがあれば実装はラクなので、Eの方針ミスを除いてもこっちの方がさっくり解けているな。