Codeforces #601 Div1 C. Point Ordering

これは割とすんなり思いつけた。
https://codeforces.com/contest/1254/problem/C

問題

2次元座標中にN個の点がある。これらの点は、最適につなぐと凸な多角形を構築できる。
以下のクエリを3N回まで用いて、凸な多角形となる点の並び順を求めよ。

• 3点を選ぶと、その3点がなす三角形の面積を答える。
• 3点を選ぶと、その3点の外積の符号を答える。

解法

まず頂点1とそこに隣接する点を求めよう。
今頂点1と頂点vが隣接点の候補とするとき、(1,v,w)の外積の符号を求める。
この符号の正負で、wが1→vのベクトルの左右どちらにあるかわかるので、例えば右側にある場合wを隣接点の候補とする、ということを繰り返せば(N-2)回のクエリで最も右側の点がわかる。

次に、(1,v)が凸多角形上で隣接していることが分かったとして、そこから一番遠い点を求めよう。
これは(1,v,w)の成す三角形のうち面積が最大のものが最も遠い。その点をdとしよう。

こうなると、1,v,d以外の点wは1→dの左右どちらかにあるか求めれば、それぞれ先ほど求めた(1,v,w)の面積を使い1に近い点がわかるので、左右それぞれ並べていけばよい。

int N;
vector<int> V;

ll ask(int T,int I,int J,int K) {
	ll ret;
	cout<<T<<" "<<(I+1)<<" "<<(J+1)<<" "<<(K+1)<<endl;
	cin>>ret;
	return ret;
}
void ans() {
	cout<<0;
	FORR(v,V) cout<<" "<<(v+1);
	cout<<endl;
	exit(0);
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	int tar=1;
	for(i=2;i<N;i++) {
		ll v=ask(2,0,tar,i);
		if(v<0) tar=i;
	}
	
	V.push_back(0);
	V.push_back(tar);
	vector<pair<ll,int>> C;
	FOR(i,N) if(i!=0 && i!=tar) {
		C.push_back({ask(1,0,tar,i),i});
	}
	sort(ALL(C));
	reverse(ALL(C));
	int t=C[0].second;
	vector<pair<ll,int>> L,R;
	for(i=1;i<C.size();i++) {
		x=ask(2,0,t,C[i].second);
		if(x<0) L.push_back(C[i]);
		else R.push_back(C[i]);
	}
	
	sort(ALL(L));
	sort(ALL(R));
	reverse(ALL(R));
	FORR(v,L) V.push_back(v.second);
	V.push_back(t);
	FORR(v,R) V.push_back(v.second);
	ans();
	
}

まとめ

シンプルでなかなか良い問題かも。