Codeforces #698 Div1 : C. Nezzar and Nice Beatmap

こちらは割と簡単。
https://codeforces.com/contest/1477/problem/C

問題

2次元座標上で、異なる位置にあるN点の座標が与えられる。
これらN点を任意の順で結んだパスを考える。
この時、始点と終点以外の各点において角度が90度未満となるようにしたい。
適切なパスの結び順を1つ答えよ。

解法

適当に凸包上の1点から始め、「直前の点から最寄りの点をどん欲に選ぶ」ということを繰り返せばよい。
仮に3点ABCがパス上で順に現れるとき、余弦定理よりAC^2=AB^2+BC^2-2AB*AC*cos∠Bとなるが、AB≧ACよりcos∠Bは確実に正、すなわち∠Bは90度未満になる。

int N;
ll X[5050],Y[5050];
int P[5050];
int vis[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int mi=0;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		if(X[i]<X[mi]) mi=i;
		if(X[i]==X[mi]&&Y[i]<Y[mi]) mi=i;
	}
	
	P[0]=mi;
	vis[mi]=1;
	FOR(i,N-1) {
		int cur=P[i];
		ll r=0;
		int tar=0;
		FOR(j,N) if(vis[j]==0) {
			ll v=(X[cur]-X[j])*(X[cur]-X[j])+(Y[cur]-Y[j])*(Y[cur]-Y[j]);
			if(v>r) r=v,tar=j;
		}
		P[i+1]=tar;
		vis[tar]=1;
	}
	
	FOR(i,N) cout<<P[i]+1<<" ";
	cout<<endl;
	
	
	
}

まとめ

本番これは割とすんなり気が付いたな。